Java_solution_in_12_ms, O(N) time and space


  • 7
    F
    import java.util.SortedSet;
    import java.util.TreeSet;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    public class Solution {
        public String rearrangeString(String str, int k) {
            if (k < 2) return str;
            int[][] times = new int[26][2];
            for(int i = 0; i < 26; i++) times[i][1] = 'a'+i;
            for (int i = 0; i < str.length(); i++) {
                times[str.charAt(i) - 'a'][0]++;
            }
            Arrays.sort(times, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]);
                }
            });
    
            int len = str.length(), maxlen = (len + k - 1)/k, count = 0, i = 0;
            if(times[0][0] > maxlen) return "";
            
            char[] res = new char[len];
            if((count = (len % k)) != 0){
                for(i = 0; i < 26; i++){
                    if(times[i][0] < maxlen) break;
                    if(i >= count) return "";
                    for(int j = i; j < len; j += k) res[j] = (char)times[i][1];
                }
            }
            
            count = i; maxlen = i;
            for(int j = 25; j >= maxlen; j--){
                for(int t = 0; t < times[j][0]; t++){
                    res[count] = (char)times[j][1];
                    count += k;
                    if(count >= len) count = ++i;
                }
            }
    
            return new String(res);
        }
    }
    

  • 0
    J

    I tried this code and struggled a bit to prove its correctness, however in this case

    "aabbccd"
    3

    current code returns "abcacdb" which 'c' violates the k = 3 distance constraint.


  • 0
    F

    @jiaodong
    Thanks. Yes, I found this problem later and forgot to post my latest solution, just a little tweak:

    import java.util.SortedSet;
    import java.util.TreeSet;
    import java.util.SortedMap;
    import java.util.TreeMap;
    public class Solution {
        public String rearrangeString(String str, int k) {
            if(k < 2) return str;
          int[] times = new int[26];
          for(int i = 0; i < str.length(); i++){
              ++times[str.charAt(i) - 'a'];
          }
          SortedSet<int[]> set = new TreeSet<int[]>(new Comparator<int[]>(){
              @Override
              public int compare(int[] a, int[] b){
                  return a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]);
              }
          });
          
          int maxtimes = 0, count = 0, maxlen = str.length() / k + ((str.length() % k == 0) ? 0 : 1);
          for(int i = 0; i < 26; i++){
              if(times[i] != 0){
                set.add(new int[]{times[i], i});
                if(times[i] > maxtimes){
                    maxtimes = times[i];
                    count = 1;
                }else if(times[i] == maxtimes){
                    ++count;
                }
              }
          }
          
          if(maxtimes > maxlen || (maxtimes == maxlen && (maxtimes - 1) * k + count > str.length()))
                return "";
          int cycles = 0;
          int cur = cycles;
          Iterator<int[]> iter = set.iterator();
          char[] res = new char[str.length()];
          while(iter.hasNext()){
              int[] e = iter.next();
              for(int i = 0; i < e[0]; i++){
                  res[cur] = (char)('a'+e[1]);
                  cur += k;
                  if(cur >= str.length()){
                      cur = ++cycles;
                  }
              }
          }
          return new String(res);
        }
    }
    

  • 1
    F

    Proposition: We just need to consider the following situations:

    1. max count of a character > (len + k - 1)/k, return "";
    2. when len % k != 0, number of chars with count (len + k -1)/k exceeds len % k, return "";
    3. Optional: if len % k != 0, for each character c with max count (len + k - 1)/k
      for(int j = i; j < len; j += k) res[j] = c;
      ++i;
      Required: For the remaining characters, their placing rules are the same when len % k == 0 or != 0; start with character c with the smallest count:
             for(int j = 0; j < count[c]; j += k) { if (j > len) j = ++i; res[j] = c;}
    

    In summary, when there is a solution, start with placing the character with count = (len + k - 1)/k when len % k != 0 if there are characters satisfying this condition, then start placing other characters in an increasing order of character count.

    This is a mathematical proof of when there is a solution and when there is none and how.

    import java.util.SortedSet;
    import java.util.TreeSet;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    public class Solution {
        public String rearrangeString(String str, int k) {
            if (k < 2) return str;
            int[][] times = new int[26][2];
            for(int i = 0; i < 26; i++) times[i][1] = 'a'+i;
            for (int i = 0; i < str.length(); i++) {
                times[str.charAt(i) - 'a'][0]++;
            }
            Arrays.sort(times, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]);
                }
            });
    
            int len = str.length(), maxlen = (len + k - 1)/k, count = 0, i = 0;
            if(times[0][0] > maxlen) return "";
            
            char[] res = new char[len];
            if((count = (len % k)) != 0){
                for(i = 0; i < 26; i++){
                    if(times[i][0] < maxlen) break;
                    if(i >= count) return "";
                    for(int j = i; j < len; j += k) res[j] = (char)times[i][1];
                }
            }
            
            count = i; maxlen = i;
            for(int j = 25; j >= maxlen; j--){
                for(int t = 0; t < times[j][0]; t++){
                    res[count] = (char)times[j][1];
                    count += k;
                    if(count >= len) count = ++i;
                }
            }
    
            return new String(res);
        }
    }
    

  • 0
    D

    you used treeset. then overall time complexity is O(NlogN). isn't it ?


  • 1
    F

    @darren5

    TreeSet only contains at most 26 entries (lower case characters). sorting takes at most O(26 log 26).


  • 0
    D

    @fatalme you are right. got it. thanks


  • 0
    P

    Fails in the below case:
    "abcdabcdabdeac"
    4
    Code output: "abcdabcdabdeac"
    d is not 4 distance apart


Log in to reply
 

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