C++ single scan O(n) solution in 38ms (99.35%), support max input string length as UINT32_MAX-3


  • 0
    B
     int firstUniqChar(string s) {
        int len = s.length();
        if (len==0) return -1;
        else if (len==1) return 0;
        else if (len==2) return s[0]==s[1] ? -1 : 0;
        else if (len>UINT32_MAX-3) return -1; // support max string length as UINT32_MAX-3
        else {
            memset(tab, 0, sizeof(tab));
    
            // scan string for duplicates
            int i = 0;
            for (char c : s) {
                switch (tab[c]) {
                    case 0:
                        tab[c] = 2 + i;
                        break;  // store first unique str index as offset+2
                    case 1:
                        break; // already has two or more duplicates
                    default:
                        tab[c] = 1;
                        break; // encounter the first duplicate
                }
                i++;
            }
    
            // scan table for the smallest duplicate index
            unsigned int min = UINT32_MAX;
            for (unsigned int t : tab) {
                if (t >= 2 && t < min) min = t;
            }
    
            // check table result
            if (min == UINT32_MAX) return -1; // not found any unique
            else return min-2;
        }
    }

  • 0
    L

    @baiyz What's your declaration of 'tab' ? Could you make a supplement about this? Thks!


  • 0
    B

    tab is short of table, which is a table to store unique 8bit Extended ASCII's offset


  • 0
    L

    @baiyz Thks!


Log in to reply
 

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