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;
        }
    };
    

  • 3
    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!

  • 1
    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)?


  • 0
    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


Log in to reply
 

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