[LC 358] Rearrange String k Distance Apart

开始的思路:

  1. Map 存每个char对应的count,
  2. List[] array 存所有count对应的字符序列,为了找到当前count最大的字符,
  3. Map存字符对应的最早可以出现的位置。

每个位置上找count最大并且可以最早出现的位置小于当前位置的字符作为最佳candidate。

思路本身可以解决这个问题。但是三个variable可以优化。

  1. Map 可以用 int[26] 代替,因为限制字符只可能是lowercase letter
  2. 没有必要,找max count的字符,可以iterate int[26]完成,因为int[]本身长度是26,所以search的time complexity是O(1).
  3. 也可以用 int[26] 代替

public String rearrangeString(String str, int k) {
    if (k == 0) return str;
    int[] map = new int[26]; // store count for each character
    for (char c : str.toCharArray()) {
        map[c - 'a']++;
    }
    StringBuilder sb = new StringBuilder();
    int[] valid = new int[26];
    for (int i = 0; i < str.length(); i++) {
        char c = findValid(map, valid, i); // find the best candidate for current location
        if (c == '#') return ""; // did not find a valid candidate
        sb.append(c);
        map[c - 'a']--; // update the count map
        valid[c - 'a'] = i+k; // store the earliest possible location for the character used in the current location
    }

    return sb.toString();

}

private char findValid(int[] map, int[] valid, int idx) {
    int max = 0;
    char c = '#';
    for (int i = 0; i < map.length; i++) {
        if (map[i] > max && idx >= valid[i]) { // find the one with max count and the earliest possible location <= current location
            c = (char) (i+'a');
            max = map[i];
        }
    }
    return c;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s