Java O(N), two array(1 frequency array , 2 last position array) solution


  • 0
    C

    Inspired by @OrlandoChen0308 in his post here https://discuss.leetcode.com/topic/48260/java-15ms-solution-with-two-auxiliary-array-o-n-time.
    I modified the code a little bit, since I am more used to use a position array to keep track of the index of a character in the new string.

    public class Solution {
        public String rearrangeString(String str, int k) {
            int [] bucket = new int [26]; 
            for (char c : str.toCharArray()) {
                ++bucket[c - 'a'];
            }
            int [] pos = new int [26];
            StringBuilder sb = new StringBuilder();
            int index = 0;
            while (index++ < str.length()) {
                int nextPos = findPos(bucket, pos, k, index);
                if (nextPos == -1) {
                    return "";
                }
                sb.append((char)('a' + nextPos));
            }
            return sb.toString();
        }
        
        private int findPos(int [] bucket, int [] pos, int k, int index) {
            int maxCount = Integer.MIN_VALUE;
            int position = -1;
            for (int i = 0; i < bucket.length; ++i) {
                if (bucket[i] > 0 && bucket[i] > maxCount && (pos[i]  == 0 || index - pos[i] >= k)) {
                    maxCount = bucket[i];
                    position = i;
                }
            }
            if (position == -1) {
                return -1;
            }
            pos[position] = index;
            --bucket[position];
            return position;
        }
    }
    

Log in to reply
 

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