# 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.

## 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: ""```

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;

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;
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);
}
}
```