<p>Given a string <code>s</code>, rearrange the characters of <code>s</code> so that any two adjacent characters are not the same.</p>

<p>Return <em>any possible rearrangement of</em> <code>s</code> <em>or return</em> <code>&quot;&quot;</code> <em>if not possible</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> "aba"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "aaab"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 500</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    string reorganizeString(string s) {
        int arr[26]={0};
        for(int i=0;i<s.size();i++)
        {
            arr[s[i]-'a']++;
        }
        int maxi=INT_MIN;
        char ch;
        for(int i=0;i<26;i++)
        {
            if(arr[i]>maxi)
            {
                maxi=arr[i];
                ch=i+'a';
            }
        }
            int index=0;
            while(maxi>0 && index<s.size())
            {
                s[index]=ch;
                maxi--;
                index+=2;
            }
            if(maxi!=0)
            {
                return "";
            }
            arr[ch-'a']=0;
            for(int i=0;i<26;i++)
            {
                 while(arr[i]>0)
                {
               index=index>=s.size() ? 1 : index;
               s[index]=i+'a';
                index+=2;
                arr[i]--;
                }

        }
        return s;
    }
};
7500