Java solution with memory efficient "limited" frequency map approach.


  • 0
    C

    While most solution create a frequency map, thats not our goal. We are only interested if an element occurs more than once. So the only frequencies that matter are 0,1 and more than 1.
    Hence I am limiting frequency to 2 and using a byte to store it, which is 4 times smaller than int. Can't use boolean since I need to store 3 types of values.

    public class Solution {
        public int firstUniqChar(String s) {
            byte[] b = new byte[26];
            int len = s.length();
            for(int i=len-1;i>-1;i--){
                int c = s.charAt(i) - 97;
                b[c] = (byte)Math.min(b[c]+1,2);       //limit frequency to 2
            }
            for(int i=0;i<len;i++){
                int c = s.charAt(i) - 97;
                if(b[c] == 1)
                    return i;
            }
            return -1;
        }
    }
    

  • 0

    @coo1k said in Frequency map solutions will fail in one scenario. Here's how to handle it.:

    if a string contains a character more than Integer.MAX_VALUE times

    As far as I've seen, that's impossible.

    Also, if it were possible, then its own length() method would be wrong, as it returns an int.


  • 0
    C

    @StefanPochmann Thanks for pointing that out. I'll correct my comments.


Log in to reply
 

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