Problem Statement:
You are given a string, you need to check if ti is possible to rearrange the string such that no two adjacent characters are same.
Example
Input: aab Output: Yes Why? You can swap the string to "aba". So no 2 adjacent characters are same.
Solution
The solution is very simple.
We need to get the character that has max repeat frequency.
Let it be max.
Then we check if max <= n-max+1, where n is the length of the string.
If it satisfies this condition, then return 1.
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> using namespace std; int check_if_possible(string str) { // to store the frequency of each character unordered_map<char, int> freq; int max_freq = 0; for (int j = 0; j < (str.length()); j++) { freq[str[j]]++; if (freq[str[j]] > max_freq) { max_freq = freq[str[j]]; } } if (max_freq <= (str.length() - max_freq + 1)) return true; return false; } // Driver code int main() { string str = "aab"; if (check_if_possible(str)) cout << "1"; else cout << "0"; return 0; }
Output:
1