Skip to content

Latest commit

 

History

History
193 lines (165 loc) · 7.07 KB

767.reorganize-string.md

File metadata and controls

193 lines (165 loc) · 7.07 KB

767. Reorganize String

Test Cases

Normal Cases

Input: s = "aab"
Output: "aba"

Edge / Corner Cases

  • It's impossible to reorganize the string.
"aaab"
"aa"
"aaaaabc"

Greedy

Intuition If we only have a and b, and the frequency a > b, then a will be more likely to be adjacent to each other. If we want to construct a string where the same characters are not adjacent, then a must be arranged in intervals a_a_a_a .... We need to arrange the character with higher frequency first avoid each other. Then we can insert the remaining characters from the intervals of a.

假設字串只有 a, b，而且字頻 a > b，那麼 a 會比 b 更容易相鄰。如果要建構一個相同字元不相鄰的字串，那麼 a 肯定要間隔排列 a_a_a_a ... 我們要讓字頻高的字元主動規避。再來剩下的字元再從 a 的間隔去安插。

貪心的思路：我們盡量先使用字頻高的字元，這樣的話讓剩下的字頻可以盡量均衡，以便後續的安插。如果我們一開始就使用字頻低的字，那麼到後面，你可以使用的字元種類就越來越少，但是該種類的字頻是高的，越容易造成相同字元相鄰的情況。所以我們會盡量在一開始的時候使用多一點字頻較高的字元，這樣才能確保我們在後面的字元選擇上有更多的選擇。

aaaaaa, bbbb, cccc

// Arrange `a`
a, _, a, _, a, _, a, _, a, _, a, _, _, _
                                    w  // write index

// Insert `b`
a, _, a, _, a, _, a, _, a, _, a, _, _, _
                                    b
   b     b     b     w

// Insert `c` 
a, b, a, b, a, b, a, _, a, _, a, _, b, _
                     c     c     c     c

When failed to reorganize the string, it's because the most frequent character is too many. If the most frequent character is more than half of the string (rounded up), it's impossible to reorganize the string.

"aaab", total (4 + 1) / 2 = 2, max = 3    X
"aab",  total (3 + 1) / 2 = 2, max = 2    O
"aab",  total (3 + 1) / 2 = 2, max = 3    X
"aa",   total (2 + 1) / 2 = 1, max = 2    X

aaaaa, bbb // total 8 characters

1  2  3  4  5  6  7  8  X  X
a, _, a, _, a, _, a, _, a, _
                        ^  ^ // Impossible to reorganize
fun reorganizeString(s: String): String {
    val count = IntArray(26)
    var maxCount = 0
    for (c in s) {
        count[c - 'a']++
        maxCount = maxOf(maxCount, count[c - 'a'])
    }
    // We check if the most frequency character is more than half of the string
    // Same as ceil(s.length / 2), we have to rounded up
    if (maxCount > (s.length + 1) / 2) return ""

    // Character to frequency pairs
    val charPairs = mutableListOf<Pair<Char, Int>>()
    for (i in 0 until 26) {
        if (count[i] > 0)
            charPairs.add(('a' + i) to count[i])
    }

    val str = CharArray(s.length)
    var write = 0
    for (pair in charPairs) {
        val c = pair.first
        var freq = pair.second
        while (freq-- > 0) {
            str[write] = c
            write += 2
            if (write >= s.length) write = 1
        }
    }
    return String(str)
}
  • Time Complexity: O(n log n), where n is the length of the string.
  • Space Complexity: O(n).

Greedy with Counting

We can optimize the above solution without sorting if we can figure out the following two questions based on the above observations:

  1. How to arrange the characters to avoid adjacent characters? We can arrange the characters at position 0, 2, 4, ... first, then 1, 3, 5, .... And we have to arrange the most frequent characters first.
  2. How to know if it's impossible to reorganize the string? As same as above, if the most frequent character is more than half of the string, it's impossible to reorganize the string.

The difference from above approach is that we don't need to sort the characters by frequency. We only need to find the most frequent character for arranging it first and checking if it's impossible to reorganize the string. The way to arrange is the same as above.

fun reorganizeString(s: String): String {
    val count = IntArray(26)
    var maxCount = 0
    var maxChar = 'a'
    for (c in s) {
        count[c - 'a']++
        if (count[c - 'a'] > maxCount) {
            maxCount = count[c - 'a']
            maxChar = c
        }
    }
    if (maxCount > (s.length + 1) / 2) return ""

    val str = CharArray(s.length)
    var write = 0
    // We must arrange the most frequent character first at position 0, 2, 4, ...
    while (count[maxChar - 'a'] > 0) {
        // Same logic as above
        str[write] = maxChar
        write += 2
        if (write >= s.length) write = 1
        count[maxChar - 'a']--
    }
    // We arrange the remaining character at position even index after 
    // the most frequent character, then restart from position 1, 3, 5, ...
    for (i in 0 until count.size) {
        val c = 'a' + i
        while (count[c - 'a'] > 0) {
            str[write] = c
            write += 2
            if (write >= s.length) {
                write = 1
            }
            count[c - 'a']--
        }
    }
    return String(str)
}
  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(n) for answer.

Greedy with Heap

Idea!! We can arrange the two different characters at the same time and we start from the most frequent characters first. In this approach, we can use max heap to get the character with the highest frequency at each iteration.

fun reorganizeString(s: String): String {
    val counts = IntArray(26)
    val maxHeap = PriorityQueue<Char>() { c1, c2 ->
        counts[c2 - 'a'] - counts[c1 - 'a']
    }
    var maxCount = 0
    for (c in s) {
        counts[c - 'a']++
        maxCount = maxOf(maxCount, counts[c - 'a'])
    }
    if (maxCount > (s.length + 1) / 2) return ""
    
    for (i in 0 until 26) {
        if (counts[i] > 0) maxHeap.add('a' + i)
    }
    
    val results = StringBuilder()
    // We poll the two most frequent characters each time
    while (maxHeap.size >= 2) {
        val c1 = maxHeap.poll()
        val c2 = maxHeap.poll()
        results.append("${c1}${c2}")
        
        val index1 = c1 - 'a'
        val index2 = c2 - 'a'
        counts[index1]--
        counts[index2]--
        if (counts[index1] > 0) maxHeap.add(c1)
        if (counts[index2] > 0) maxHeap.add(c2)
    }

    // There is only one character left, we can take that only one character
    if (maxHeap.isNotEmpty()) {
        results.append("${maxHeap.poll()}")
    }
    return results.toString()
}
  • Time Complexity: O(n log n), where n is the length of the string.
  • Space Complexity: O(n).

References