Java 15ms Solution with Two auxiliary array. O(N) time.


  • 67

    This is a greedy problem.
    Every time we want to find the best candidate: which is the character with the largest remaining count. Thus we will be having two arrays.
    One count array to store the remaining count of every character. Another array to keep track of the most left position that one character can appear.
    We will iterated through these two array to find the best candidate for every position. Since the array is fixed size, it will take constant time to do this.
    After we find the candidate, we update two arrays.

    public class Solution {
        public String rearrangeString(String str, int k) {
            int length = str.length();
            int[] count = new int[26];
            int[] valid = new int[26];
            for(int i=0;i<length;i++){
                count[str.charAt(i)-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int index = 0;index<length;index++){
                int candidatePos = findValidMax(count, valid, index);
                if( candidatePos == -1) return "";
                count[candidatePos]--;
                valid[candidatePos] = index+k;
                sb.append((char)('a'+candidatePos));
            }
            return sb.toString();
        }
        
       private int findValidMax(int[] count, int[] valid, int index){
           int max = Integer.MIN_VALUE;
           int candidatePos = -1;
           for(int i=0;i<count.length;i++){
               if(count[i]>0 && count[i]>max && index>=valid[i]){
                   max = count[i];
                   candidatePos = i;
               }
           }
           return candidatePos;
       }
    }
    

    At first I was considering using PriorityQueue and referring to this post:
    c++ unordered_map priority_queue solution using cache
    I have doubts for this solution. If we have "abba", k=2; It seems we might end up with "abba" as the result. Since in the second while loop, I'm not sure 'a' or 'b' will be polled out first.
    In Java, when two keys in PriorityQueue have same value, there is no guarantee on the order poll() will return. But I'm not sure how heap is implemented in C++.


  • 6
    M

    for priorityqueue, if counts are same, you can compare the letter, so the order for polling out will be consistant.


  • 0

    That makes sense! Thanks.


  • 1
    E

    Am I missing something? This looks like O(N^2) time because findValidMax() is linear.


  • 1

    @ericcire Since the array is fixed size(26), it will take constant time to find max


  • 0
    E

    @OrlandoChen0308 I cannot believe I missed that. Thanks.


  • 0

    good solution

    tricky to come with these two auxiliary arrays


  • 0
    Z
    This post is deleted!

  • 0
    C

    Because PriorityQueue can not handle duplicate, I used TreeMap, which made codes very complicated. Your solution is much better. I feel greedy solution is really hard to get. How did you come with it?!


  • 0
    I

    I use String instead of StringBuilder, but it can't pass the new test case "aaa......zzz" 26 TLE


  • 0
    H
    This post is deleted!

  • 2

    @OrlandoChen0308
    Great work!!!
    You can add

    if (k > 26) {
        return "";
    }
    

    to avoid unnecessary computation!


  • 1
    S

    said in Java 15ms Solution with Two auxiliary array. O(N) time.:

    One count array to store the remaining count of every character. Another array to keep track of the most left position that one character can appear.

    how could we prove greedy works here


  • 0
    S

    I like your code.
    It's simple and doesn't need comments because the code is the documentation.
    Found it easy to read and understand.


  • 0

    said in Java 15ms Solution with Two auxiliary array. O(N) time.:

    Can someone explain why we are comparing index>=valid[i] in findValidMax.
    Thanks.


  • 1
    P

    Is it possible to give a proof of correctness/optimality for the greedy algorithm?


  • 0
    A

    @McGar I tried the priorityqueue, it is slower. due to the fact that we need to poll k values each time and use them once in order and put them back.


  • 1
    C

    @surindersokhal110gmail.com say, we are choosing the 5th best candidate. if we consider 0th character(='a') to be a potential candidate but its next valid position is 7, then it cannot be the 5th best candidate. Hence, valid[i] <= index.


  • 1
    O

    Excellent solution! I further modified your code a little so that the total run time can be reduced to 8 ms. Thank you for your idea.

    public String rearrangeString(String str, int k) {
        if (str == null || k < 2) { return str; }
        int[] validPosition = new int[26];
        int[] letterCounts = new int[26];
        char[] res = new char[str.length()];
        for (char c : str.toCharArray()) {
            letterCounts[c - 'a']++;
        }
        int n = str.length();
        for (int i = 0; i < n; i++) {
            int nextLetter = findNext(letterCounts, validPosition, i);
            if (nextLetter == -1) {
                return "";
            }
            res[i] = (char) ('a' + nextLetter);
            validPosition[nextLetter] = i + k;
            letterCounts[nextLetter]--;
        }
        return new String(res);
    }
    
    public int findNext(int[] letterCounts, int[] validPosition, int index) {
        int max = 0, res = -1;
        for (int i = 0; i < 26; i++) {
            if (letterCounts[i] > max && validPosition[i] <= index) {
                res = i;
                max = letterCounts[i];
            }
        }
        return res;
    }

  • 0
    W

    @odingg Similar idea in C++, but I think my solution is more scalable for any characters, because I maintain a max-heap for the character, and its count and next valid position. So, we do not need to iterate over the space of characters.

    class Solution {
    public:
        struct Node {
            int count, validPos;
            char ch;
            Node(int count, int validPos, char ch): count(count), validPos(validPos), ch(ch) {}
        };
        
        string rearrangeString(string str, int k) {
            vector<int> mp(26, 0);
            for(char c: str) mp[c-'a']++;
            auto mycomp = [&](const Node& node1, const Node& node2) {return node1.count > node2.count;};
            multiset<Node, decltype(mycomp)> heap(mycomp);
            for(int i = 0; i < 26; i++)
                if(mp[i] != 0) heap.insert(Node(mp[i], 0, i+'a'));
            string rt = "";
            for(int i = 0; i < str.size(); i++) {
                auto iter = heap.begin();
                for(; iter != heap.end() && i < iter->validPos; iter++) {}
                if(iter == heap.end()) return "";
                rt += iter->ch;
                Node cand(iter->count-1, i+k, iter->ch);
                heap.erase(iter);
                if(cand.count > 0) heap.insert(cand);
            }
            return rt;
        }
    };
    

Log in to reply
 

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