← Static tasks

358. Rearrange String k Distance Apart

leetcode hard

#csharp#hard#hash-table#leetcode#math#string

Task

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3

Output: "abcabc"

Explanation: The same letters are at least a distance of 3 from each other.

C# solution

matched/original
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class Solution {
    public string RearrangeString(string s, int k) {
        var freqs = new Dictionary<char, int>();
        int maxFreq = 0;
        
        foreach (var c in s) {
            if (!freqs.ContainsKey(c)) {
                freqs[c] = 0;
            }
            freqs[c]++;
            maxFreq = Math.Max(maxFreq, freqs[c]);
        }
        
        var mostChars = new HashSet<char>();
        var secondChars = new HashSet<char>();
        
        foreach (var kvp in freqs) {
            if (kvp.Value == maxFreq) {
                mostChars.Add(kvp.Key);
            } else if (kvp.Value == maxFreq - 1) {
                secondChars.Add(kvp.Key);
            }
        }
        
        var segments = new StringBuilder[maxFreq];
        for (int i = 0; i < maxFreq; i++) {
            segments[i] = new StringBuilder();
            foreach (var c in mostChars) {
                segments[i].Append(c);
            }
            if (i < maxFreq - 1) {
                foreach (var c in secondChars) {
                    segments[i].Append(c);
                }
            }
        }
        
        int segmentId = 0;
        
        foreach (var kvp in freqs) {
            var c = kvp.Key;
            var freq = kvp.Value;
            
            if (mostChars.Contains(c) || secondChars.Contains(c)) {
                continue;
            }
            
            while (freq-- > 0) {
                segments[segmentId].Append(c);
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }
        
        for (int i = 0; i < maxFreq - 1; i++) {
            if (segments[i].Length < k) {
                return "";
            }
        }
        
        return string.Join("", segments.Select(sb => sb.ToString()));
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string RearrangeString(string s, int k) {
        var freqs = new unordered_map<char, int>();
        int maxFreq = 0;
        
        foreach (var c in s) {
            if (!freqs.count(c)) {
                freqs[c] = 0;
            }
            freqs[c]++;
            maxFreq = max(maxFreq, freqs[c]);
        }
        
        var mostChars = new HashSet<char>();
        var secondChars = new HashSet<char>();
        
        foreach (var kvp in freqs) {
            if (kvp.Value == maxFreq) {
                mostChars.push_back(kvp.Key);
            } else if (kvp.Value == maxFreq - 1) {
                secondChars.push_back(kvp.Key);
            }
        }
        
        var segments = new StringBuilder[maxFreq];
        for (int i = 0; i < maxFreq; i++) {
            segments[i] = new StringBuilder();
            foreach (var c in mostChars) {
                segments[i].Append(c);
            }
            if (i < maxFreq - 1) {
                foreach (var c in secondChars) {
                    segments[i].Append(c);
                }
            }
        }
        
        int segmentId = 0;
        
        foreach (var kvp in freqs) {
            var c = kvp.Key;
            var freq = kvp.Value;
            
            if (mostChars.Contains(c) || secondChars.Contains(c)) {
                continue;
            }
            
            while (freq-- > 0) {
                segments[segmentId].Append(c);
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }
        
        for (int i = 0; i < maxFreq - 1; i++) {
            if (segments[i].size() < k) {
                return "";
            }
        }
        
        return string.Join("", segments.Select(sb => sb.ToString()));
    }
}

Java solution

matched/original
class Solution {
    public String rearrangeString(String s, int k) {
        Map<Character, Integer> freqs = new HashMap<>();
        int maxFreq = 0;
        
        for (char c : s.toCharArray()) {
            freqs.put(c, freqs.getOrDefault(c, 0) + 1);
            maxFreq = Math.max(maxFreq, freqs.get(c));
        }

        Set<Character> mostChars = new HashSet<>();
        Set<Character> secondChars = new HashSet<>();
        
        for (char c : freqs.keySet()) {
            if (freqs.get(c) == maxFreq) mostChars.add(c);
            else if (freqs.get(c) == maxFreq - 1) secondChars.add(c);
        }

        StringBuilder[] segments = new StringBuilder[maxFreq];
        for (int i = 0; i < maxFreq; i++) segments[i] = new StringBuilder();

        for (char c : mostChars) {
            for (int i = 0; i < maxFreq; i++) segments[i].append(c);
        }
        for (char c : secondChars) {
            for (int i = 0; i < maxFreq - 1; i++) segments[i].append(c);
        }

        int segmentId = 0;
        for (char c : freqs.keySet()) {
            if (mostChars.contains(c) || secondChars.contains(c)) continue;
            for (int freq = freqs.get(c); freq > 0; freq--) {
                segments[segmentId].append(c);
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }

        for (int i = 0; i < maxFreq - 1; i++) {
            if (segments[i].length() < k) return "";
        }

        return String.join("", segments);
    }
}

JavaScript solution

matched/original
var rearrangeString = function(s, k) {
    let freqs = {};
    let maxFreq = 0;

    for (let char of s) {
        freqs[char] = (freqs[char] || 0) + 1;
        maxFreq = Math.max(maxFreq, freqs[char]);
    }

    let mostChars = new Set();
    let secondChars = new Set();

    for (let char in freqs) {
        if (freqs[char] === maxFreq) {
            mostChars.add(char);
        } else if (freqs[char] === maxFreq - 1) {
            secondChars.add(char);
        }
    }

    let segments = Array.from({ length: maxFreq }, () => []);

    for (let i = 0; i < maxFreq; i++) {
        for (let char of mostChars) {
            segments[i].push(char);
        }
        if (i < maxFreq - 1) {
            for (let char of secondChars) {
                segments[i].push(char);
            }
        }
    }

    let segmentId = 0;

    for (let char in freqs) {
        if (mostChars.has(char) || secondChars.has(char)) {
            continue;
        }

        for (let freq = freqs[char]; freq > 0; freq--) {
            segments[segmentId].push(char);
            segmentId = (segmentId + 1) % (maxFreq - 1);
        }
    }

    for (let i = 0; i < maxFreq - 1; i++) {
        if (segments[i].length < k) {
            return "";
        }
    }

    return segments.flat().join("");
}

Python solution

matched/original
from collections import defaultdict

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = defaultdict(int)
        max_freq = 0
        
        for char in s:
            freqs[char] += 1
            max_freq = max(max_freq, freqs[char])
        
        most_chars = {char for char, freq in freqs.items() if freq == max_freq}
        second_chars = {char for char, freq in freqs.items() if freq == max_freq - 1}
        
        segments = [list() for _ in range(max_freq)]
        
        for i in range(max_freq):
            for char in most_chars:
                segments[i].append(char)
            if i < max_freq - 1:
                for char in second_chars:
                    segments[i].append(char)
        
        segment_id = 0
        
        for char, freq in freqs.items():
            if char in most_chars or char in second_chars:
                continue
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)
        
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""
        
        return "".join("".join(segment) for segment in segments)

Go solution

matched/original
import (
    "strings"
)

func rearrangeString(s string, k int) string {
    freqs := make(map[byte]int)
    maxFreq := 0
    
    for i := 0; i < len(s); i++ {
        freqs[s[i]]++
        if freqs[s[i]] > maxFreq {
            maxFreq = freqs[s[i]]
        }
    }
    
    mostChars := make(map[byte]bool)
    secondChars := make(map[byte]bool)
    
    for c, freq := range freqs {
        if freq == maxFreq {
            mostChars[c] = true
        } else if freq == maxFreq-1 {
            secondChars[c] = true
        }
    }
    
    segments := make([]strings.Builder, maxFreq)
    
    for i := 0; i < maxFreq; i++ {
        for c := range mostChars {
            segments[i].WriteByte(c)
        }
        if i < maxFreq-1 {
            for c := range secondChars {
                segments[i].WriteByte(c)
            }
        }
    }
    
    segmentId := 0
    
    for c, freq := range freqs {
        if mostChars[c] || secondChars[c] {
            continue
        }
        
        for freq > 0 {
            segments[segmentId].WriteByte(c)
            segmentId = (segmentId + 1) % (maxFreq - 1)
            freq--
        }
    }
    
    for i := 0; i < maxFreq-1; i++ {
        if segments[i].Len() < k {
            return ""
        }
    }
    
    var result strings.Builder
    for i := 0; i < maxFreq; i++ {
        result.WriteString(segments[i].String())
    }
    
    return result.String()
}

Explanation

Algorithm

Создайте словарь частот для символов строки и определите максимальную частоту.

Разделите символы на группы по частоте и создайте сегменты для размещения символов.

Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎