Skip to main content

Rearrange String k Distance Apart

Question​

Given a string s and an integer k, rearrange the string such that every substring of length k is lexicographically ordered and the concatenation of all the substrings is equal to s.

Example 1
None

Solution​

all//Rearrange String k Distance Apart.py


import collections

def rearrangeStringKDistanceApart(s, k):
    if k == 0:
        return s
    max_freq = collections.Counter(s).most_common(1)[0][1]
    max_char = collections.Counter(s).most_common(1)[0][0]

    if (len(s) < (max_freq - 1) * (k + 1) + 1):
        return ""

    res = [max_char] * max_freq
    used = [False] * len(s)

    for i in range(max_freq):
        pointer = i
        while used[pointer]:
            pointer += 1
        res[i] = s[pointer]
        used[pointer] = True

    pointer = max_freq
    for i in range(len(s)):
        if s[i] != max_char and not used[i]:
            while used[pointer]:
                pointer += 1
            if pointer - i > k:
                return ""
            res.insert(pointer, s[i])
            used[pointer] = True
            pointer += 1

    return "".join(res)

# Test
s = "aabbcc"
k = 3

print(rearrangeStringKDistanceApart(s, k))
# Output: ababcc