Java 12 ms easy understanding with StringBuilder[]


  • 0
    D
    public class Solution {
        public String rearrangeString(String str, int k) {
            if (k < 1 || str == null || str.length() < 2) {
                return str;
            }
            
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                ++count[c - 'a'];
            }
            
            PriorityQueue<Character> q = new PriorityQueue<>(26, new Comparator<Character>() {
                @Override
                public int compare(Character c1, Character c2) {
                    int num1 = count[c1 - 'a'];
                    int num2 = count[c2 - 'a'];
                    if (num1 == num2) {
                        return c1 - c2;
                    }
                    return num1 > num2 ? -1 : 1;
                }
            });
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    q.offer((char) ('a' + i));
                }
            }
            
            int n = count[q.peek() - 'a'];
            StringBuilder[] sbs = new StringBuilder[n];
            for (int i = 0; i < n; i++) {
                sbs[i] = new StringBuilder();
            }
            
            int idx = 0;
            while (!q.isEmpty()) {
                char c = q.poll();
                int num = count[c - 'a'];
                if (num == n) {
                    allocateAll(c, sbs);
                } else {
                    idx = allocate(c, num, idx, sbs);
                }
            }
    
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (i < n - 1 && sbs[i].length() < k) {
                    return "";
                }
                res.append(sbs[i]);
            }
            return res.toString();
        }
        
        private void allocateAll(char c, StringBuilder[] sbs) {
            for (StringBuilder sb : sbs) {
                sb.append(c);
            }
        }
        
        private int allocate(char c, int num, int idx, StringBuilder[] sbs) {
            int n = sbs.length;
            while (num-- > 0) {
                sbs[idx].append(c);
                if (idx == n - 2) {
                    idx = 0;
                } else {
                    ++idx;
                }
            }
            return idx;
        }
    }
    

Log in to reply
 

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