Use PriorityQueue for this question


  • 0
    Y
    1. read character from right to left
    2. if this character haven't been read. put it into heap and add pos to map
    3. if we have read this character, update array map with -1, and remove the pos of this character from heap
      Last step: return the top value from heap Or return -1 if heap isEmpty
    public class Solution {
    
        public int firstUniqChar(String s) {
            if(s.length() == 0)
                return -1;
            PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
            int[] findDup = new int[26];
            for(int i=s.length()-1; i>=0; i--){
                int letterPos = s.charAt(i) - 'a';
                if(findDup[letterPos] == 0){
                    findDup[letterPos] = i;
                    heap.add(i);
                }else{
                    if(findDup[letterPos] > 0){
                        int lastPos = findDup[letterPos];
                        findDup[letterPos] = -1;
                        heap.remove(lastPos);
                    }
                }
            }
            if(heap.isEmpty())
                return -1;
            return heap.remove();
        }
    }
    

Log in to reply
 

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