C++ 2 solutions


  • 13
    D

    Brute force solution, traverse string s 2 times. First time, store counts of every character into the hash table, second time, find the first character that appears only once.

    class Solution {
    public:
        int firstUniqChar(string s) {
            unordered_map<char, int> m;
            for (auto &c : s) {
                m[c]++;
            }
            for (int i = 0; i < s.size(); i++) {
                if (m[s[i]] == 1) return i;
            }
            return -1;
        }
    };
    

    if the string is extremely long, we wouldn't want to traverse it twice, so instead only storing just counts of a char, we also store the index, and then traverse the hash table.

    class Solution {
    public:
        int firstUniqChar(string s) {
            unordered_map<char, pair<int, int>> m;
            int idx = s.size();
            for (int i = 0; i < s.size(); i++) {
                m[s[i]].first++;
                m[s[i]].second = i;
            }
            for (auto &p : m) {
                if (p.second.first == 1) idx = min(idx, p.second.second);
            }
            return idx == s.size() ? -1 : idx;
        }
    };
    

  • 4
    S

    Inspired by your idea.

    class Solution {
    public:
        int firstUniqChar(string s) {
            std::pair<int, int> counts[26];
            
            int n = s.size();
            for (int i = 0; i < n; i++) {
                int pos = s[i] - 'a';
                counts[pos].first++;
                counts[pos].second = i;
            }
            
            int index = n;
            
            for (int i = 0; i < 26; i++) {
                if (counts[i].first == 1) {
                    index = std::min(index, counts[i].second);
                }    
            }
            
            return (index == n) ? -1 : index;
        }
    };
    

  • -1
    A

    @dr.pro If this is brute force, is there an optimal solution?


  • 0
    S
    This post is deleted!

  • 2
    S

    @dr.pro first solution worst complexity is 2N (N = s.size(), iterate string 2 times), second solution worst complexity is 2N + 26 (iterate string 1 time but every time 2 operations, plus iteration through hash map)?


  • 1
    M

    Another way to traverse the string only once.

    You can use hashmap to store the index of non-duplicated numbers. For duplicates, save the index as INT_MAX. Return the minimum index.

    
    class Solution {
    public:
        int firstUniqChar(string s) {
            unordered_map<char, int> mymap;
            int ans = INT_MAX;
            for(int i = 0; i < s.size(); i++){
                if(mymap.find(s[i]) == mymap.end()){
                    mymap[s[i]] = i;
                }
                else{
                    mymap[s[i]] = INT_MAX;
                }
            }
            for(auto it : mymap){
                ans = min(it.second, ans);
            }
            return (ans == INT_MAX)? -1 : ans;
        }
    };
    

  • 0
    A

    class Solution {
    public:
    int firstUniqChar(string s) {

        int i;
        vector<char> v(s.begin(),s.end());
            for(i=0;i<v.size();i++)
            {
                char tmp=v[i];
                v.erase(v.begin()+i);
                if(find(v.begin(),v.end(),tmp)==v.end())
                    return i;
                v.insert(v.begin()+i,tmp); 
                
            }
        return -1;
    }
    

    };
    using vector its to simple


  • 0
    S

    @dr.pro I'm wondering for unordered_map, won't the elements go out of order? Then we won't be able to find the first character that appears only once.


  • 0
    D

    @sunfruit
    if(p.second.first == 1) idx = min(idx, p.second.second); this solves the problem


  • 0
    S

    @dr.pro sorry, I misread your solution


  • 0
    Y

    @akki9 Have you thought about time complexity? It looks like the worst case is O(n^2) to me


  • 0
    G

    @dr.pro The second solution is no good than the first, cause there are two operations, save the index, and increase the count. when you traverse the string, it turns out to be 2*N operations, which is the worse case in the first solution, and this is not counting the map overhead. So the second solution's best case is first solution's worst case, and on average the first is faster than second.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.