O(N) Greedy solution using heap with farthest from current position and remaining frequency count tie breaker


  • 0
    J

    We keep a heap of the characters appearing in the string more then once (only 1 instance of such characters will ever be in the heap at a given time) and since the alphabet size is fixed heap operations can be considered to O(1). For our problem there will never be more then 26 elements in the heap and so heap ops can be considered constant. We order the heap on oldest seen and frequency and we keep a standard queue of the characters appearing once to be tried when no valid element can be used on the heap (last seen is closer then k, or no more elements). When we remove an element from the heap and there are still instances of that character available we add another instance of that character with the last seen index (current position) and the remaining frequency.

    static class CharIdxPair implements Comparable<CharIdxPair> {
        	char c;
        	int lastSeenIdx, freq;
        
        	public CharIdxPair(char c, int lastSeenIdx, int freq) {
        		this.c = c;
        		this.lastSeenIdx = lastSeenIdx;
        		this.freq = freq;
        	}
        
        	public CharIdxPair(char c, int freq) {
        		this(c, -1, freq);
        	}
        
        	/**
        	 * Elements on the heap are ordered in ascending order of last used position indices therefore enabling 
        	 * an ordering of farthest from the current position to fill. We also break ties by ordering in descending order
        	 * elements by remaining frequency count
        	 * 
        	 * @param v
        	 * @return
        	 */
        	@Override
        	public int compareTo(CharIdxPair v) {
        		if(this.lastSeenIdx == v.lastSeenIdx)
        			return v.freq - this.freq;
        		else
        			return this.lastSeenIdx - v.lastSeenIdx;
        	}
        }
        
        public static String rearrangeString(String str, int k) {
        	char[] cstr = str.toCharArray();
        	int[] freq = new int[256];
        	PriorityQueue<CharIdxPair> pq = new PriorityQueue<>();
        	Queue<Character> q = new ArrayDeque<>();
        
        	int n = str.length();
        
        	for (int i = 0; i < n; i++) {
        		freq[cstr[i]]++;
        	}
        
        	Set<Character> seen = new HashSet<>();
        	for (int i = 0; i < n; i++) {
        		if (seen.contains(cstr[i])) continue;
        		
        		seen.add(cstr[i]);
        
        		if (freq[cstr[i]] == 1) {
        			q.add(cstr[i]);
        		} else {
        			// > 1
        			pq.add(new CharIdxPair(cstr[i], freq[cstr[i]]));
        		}
        	}
        
        	char[] buff = new char[n];
        	int p = 0;
        	while (p < n) {
        		
        		if (pq.size() == 0 && q.size() == 0) return "";
        		else if (pq.size() == 0) {
        			buff[p++] = q.poll();
        			continue;
        		}
        		
        		CharIdxPair cip = pq.peek();
        
        		if (cip.lastSeenIdx >= 0 && p - cip.lastSeenIdx < k) {
        			if (q.size() == 0) return "";
        			buff[p] = q.poll();
        		} else {
        			cip = pq.poll();
        			buff[p] = cip.c;
        
        			freq[cip.c]--;
        
        			if (freq[cip.c] > 0) {
        				pq.add(new CharIdxPair(cip.c, p, freq[cip.c]));
        			}
        		}
        
        		p++;
        	}
        
        	return new String(buff);
        }

  • 0
    J

    I added the remaining frequency count tie breaker to the ordering of heap elements after observing some WA and making an educated guess. I still don't have a proof as to why using the remaining frequency as a tie breaker is correct. My greedy algorithm proof knowledge could be stronger so if somebody can elaborate that would be helpful thank you!


Log in to reply
 

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