358. Rearrange String k Distance Apart
Дана строка 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# решение
сопоставлено/оригинал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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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()
}Algorithm
Создайте словарь частот для символов строки и определите максимальную частоту.
Разделите символы на группы по частоте и создайте сегменты для размещения символов.
Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.