How to Reorganize String?

INTRODUCTION

In this article, we will see about How to Reorganize String? It is one of the interesting problem, Reorganizing string.

Background

Day 13 of 100 Days of Leetcode Programming Challenge. This is one of the top Leetcode Problem. This problem tests our knowledge in string manipulations and hashing.

Related Problems

LANGUAGE

I took C# programming language to solve this problem. Since language is independent of the problem. You can use whatever language you wish to solve. Only problem solving approach(logic) is important.

Problem

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Please try

Before seeing the solution approach, I recommend you to solve this problem by your own. Take 5 to 10 minutes. Try to come with solution. It can be anything, brute force approach or any other approach you like. Comment your approach below, so it will be helpful to others.

Solution Approach

Input: S = "aaabbbccdd"

1. Count the letter frequencies and store in hash[i]

        int[] hash = new int[26];

        for (int i = 0; i < S.Length(); i++) {
            hash[S[i] - 'a']++;
        } 

2. Find the Letter with largest occurrence

        int max = 0, letter = 0;

        for (int i = 0; i < hash.Length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
Input: S = "aaabbbccdd"

1) Count the letter frequencies and store it in hash[i]

2) max = 0, letter = 0;

        for (int i = 0; i < hash.Length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }

So max becomes 3, letter = 0; ('a' have the maximum frequency of 3)

3. put the letter into even index number (0, 2, 4 …) char array

        char[] res = new char[S.Length()];

        int index = 0;

        while (hash[letter] > 0) {
            res[index] = (char) (letter + 'a');
            index += 2;
            hash[letter]--;
        }
3) char[] res = new char[S.Length()];

_ _ _ _ _ _ _ _ _ _

        int index = 0;

        while (hash[letter] > 0) 
        {
            res[index] = (char) (letter + 'a');
            index += 2;
            hash[letter]--;
        }

a _ a _ a _ _ _ _ _

4. put the rest into the array

        for (int i = 0; i < hash.Length; i++) {
            while (hash[i] > 0) {
                if (index >= res.Length) {
                    index = 1;
                }
                res[index] = (char) (i + 'a');
                index += 2;
                hash[i]--;
            }
        }
      res = a _ a _ a _ _ _ _ _
  

      for (int i = 0; i < hash.Length; i++) {
            while (hash[i] > 0) {
                if (index >= res.Length) {
                    index = 1;
                }
                res[index] = (char) (i + 'a');
                index += 2;
                hash[i]--;
            }
        }


      res = a b a c a c b d b d

Solution

  public class Solution {
  
      public string ReorganizeString(string S) {
        
        int[] hash = new int[26];
        for(int i=0;i<S.Length;i++)
        {
            hash[S[i]-'a']++;
        }
        
        int letter = 0, max = 0;
        for(int i=0;i<26;i++)
        {
            if(hash[i] > max)
            {
                max = hash[i];
                letter = i;
            }
        }
        
        //Breaking Condition
        if(max > (S.Length+1)/2)
            return "";
        
        char[] res = new char[S.Length];
        int index = 0;
        
        while(hash[letter] > 0)
        {
            if(index >= res.Length)
                index= 1;
            res[index] = (char)(letter+'a');
            index += 2;
            hash[letter]--;
        }
        
        for(int i=0;i<26;i++)
        {
            while(hash[i] > 0)
            {
                if(index >= res.Length)
                    index = 1;
                res[index] = (char)(i+'a');
                hash[i]--;
                index += 2;
            }
        }
         return new String(res);
    }
}

Time Complexity: O(n)

Space Complexity : O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s