Java bit manipulation solution (no additional space)


  • 0
    A

    There are 3 states that need to be tracked -

    1. Character present / not present in the string
    2. Character present only once in the string
    3. Character present more than once in the string

    This solution uses an integer 'pr' to track presence of character in the string and 'cnt' to track number of occurrences (1 or >1) of character in the string.

    There are 2 passes involved, though the second pass could technically be replaced by a loop iterating 'a' through 'z' and tracking min index of characters with 1 occurence. Also, using additional space or more integers could probably replace the second pass.

    This solution works because we only consider lowercase letters.

    public int firstUniqChar(String s) {
            
            if(s == null || s.isEmpty())
                return -1;
    
            int pr = 0; //if a bit is 1, corresponding char is present in the string
            int cnt = 0; //if a bit is 1, corresponding char is present only once in the string 
            for(int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i);
                int mask = (1 << (c - 'a'));
                if((cnt & mask) == 0 && (pr & mask) > 0)
                    continue;
                else if ((cnt & mask) == 0 && (pr & mask) == 0)
                {
                    cnt |= mask;   //set the bit
                }
                else if ((cnt & mask) > 0 && (pr & mask) > 0)
                {
                    cnt &= ~mask;  //reset the bit              
                }                
                pr |= mask;  //mark presence in the string
            }
            
            for(int i = 0; i < s.length(); i++)
            {
                int mask = 1 << (s.charAt(i) - 'a');
                if((pr & mask) > 0 && (cnt & mask) > 0)
                    return i;
            }
            return -1;               
        }
    

Log in to reply
 

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