Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Rearrange String

Problem Statement

Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.

Example 1:

Input: "aappp"
Output: "papap"
Explanation: In "papap", none of the repeating characters come next to each other.

Example 2:

Input: "Programming"
Output: "rgmrgmPiano" or "gmringmrPoa" or "gmrPagimnor", etc.
Explanation: None of the repeating characters come next to each other.

Example 3:

Input: "aapa"
Output: ""
Explanation: In all arrangements of "aapa", atleast two 'a' will come together e.g

.....

.....

.....

Like the course? Get enrolled and start learning!
N

NEHA GUPTA

· 4 years ago

hi

R

Rishik Lad

· 4 years ago

There's a typo in the Python solution here:

previousFrequency = frequency + 1 when it should be subtracting 1 instead.

Show 1 reply
U

Utkarsh Gupta

· 3 years ago

If we create the frequency map and then iterate through the values of the map. Each iteration the minimum number of characters required for the current key will be T1-1 where T1 is the count of characters of current key. Now for frequency of next character will be reduced from T2 to T2-(T1-1). T2` = T2-(T1-1)-1 will be the remaining frequency of next character so we can repeat the same procedure and at the end if we are left with 0,1 or 2 then it is possible to create a string with all the characters such that no two same characters are adjacent.

Could this be a possible solution?

Show 1 reply
Josh Osborne

Josh Osborne

· 2 years ago

I keep trying to work through why the solution code will ensure that if we have a result string of length equal to the input string it assumes we correctly interlaced the characters. If you feed in "AAAA" the result string will come out as "AAAA" and have the same length as the input string when we want it to output and empty string.

We can simply check if the char == prevChar and return the empty string if thats the case.

What am I not understanding?

Here's how I would amend the while loop:

while maxHeap:
      freq,char = heappop(maxHeap)
      if char == prevChar:
        return ""
      resultString.append(char)
      if prevChar and -prevFreq > 0:
        heappush(maxHeap,[prevFreq,prevChar])
      prevChar = char
      prevFreq = freq + 1
Rishabh Shukla

Rishabh Shukla

· 2 years ago

from collections import Counter
from heapq import *

class Solution:
  def rearrangeString(self, str1):
    
    freqs = sorted(list(Counter(str1).items()), key=lambda x: x[1], reverse=True)

    res = ""

    prev_char = None

    while freqs:
      i = 0
      while i < len(freqs):
        char, freq = freqs[i]

        if prev_char and prev_char == char:
          return ""

        res += char
        freqs[i] = (char, freq - 1)

        prev_char = char

        if freqs[i][1] == 0:
          del freqs[i]

        i += 1
        
    return res
Show 1 reply
Tobby Lie

Tobby Lie

· 2 years ago

Since the maximum number of characters in the alphabet is fixed and has an upper bound, can't we say that the time complexity is just O(nlog(1)) which simplifies to O(n)? Or at the very least, it would be O(nlog(k)) where k << n since at any given time, the heap can only store a max of k characters.

Show 1 reply
L

lejafilip

· 2 years ago

Here you have solution for frequentMap + odd/even approach. Just fill every even with the biggest.

        std::unordered_map<char, int> frequentMap;
        for(const auto& ch : s)
        {
            frequentMap[ch]++;
        }

        auto biggestChar = 'a';
        auto biggestCount = 0;

        for(const auto& [ch, count] : frequentMap)
        {
            if(biggestCount < count)
            {
                biggestChar = ch;
                biggestCount = count;
            }
        }

        frequentMap.erase(biggestChar);

        std::string result(s.size(),' ');
        for(auto i = 0; i < result.size(); i+=2)
        {
            if(biggestCount == 0)
            {
                auto ch = frequentMap.begin()->first;
                result[i] = ch;
P

Pete Stenger

· 2 years ago

from heapq import *
from collections import Counter
import math

class Solution:
  def rearrangeString(self, str1):
    counts = Counter(str1)
    heap = [
      (-value, char) for char, value in counts.items()
    ]
    heapify(heap)
    if -heap[0][0] > len(str1)//2:
      return ''
    
    res = '_' * len(str1)
    i = 0
    while heap:
      count, char = heappop(heap)
      while count < 0:
        res[i] = char
        i += 2
        if i >= len(res):
          i = 1
        count += 1
    return res
Show 1 reply