coding-Interview/RearrangeKDistanceApart.java at master · arjunmullick/coding-Interview · GitHub

History

51 lines (45 loc) · 1.31 KB

Raw

/**

* Example 1:

Input: s = "aabbcc", k = 3

Output: "abcabc"

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

Example 2:

Input: s = "aaabc", k = 3

Output: ""

Explanation: It is not possible to rearrange the string.

Example 3:

Input: s = "aaadbbcc", k = 2

Output: "abacabcd"

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

**/

class Solution {

public String rearrangeString(String s, int k) {

int n = s.length();

int[] cnt = new int[26];

for (char c : s.toCharArray()) {

++cnt[c - 'a'];

}

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);

for (int i = 0; i < 26; ++i) {

if (cnt[i] > 0) {

pq.offer(new int[] {cnt[i], i});

}

Deque<int[]> q = new ArrayDeque<>();

StringBuilder ans = new StringBuilder();

while (!pq.isEmpty()) {

var p = pq.poll();

int v = p[0], c = p[1];

ans.append((char) ('a' + c));

q.offer(new int[] {v - 1, c});

if (q.size() >= k) {

p = q.pollFirst();

if (p[0] > 0) {

pq.offer(p);

}

return ans.length() == n ? ans.toString() : "";

}

coding-Interview/RearrangeKDistanceApart.java at master · arjunmullick/coding-Interview · GitHub

Expand file tree

Breadcrumbs

RearrangeKDistanceApart.java

Latest commit

History

Breadcrumbs

RearrangeKDistanceApart.java

File metadata and controls