Reformat The String - Leetcode Solution

Problem Statement:

Given a string s containing only lowercase letters, we need to reformat the string such that no two adjacent characters are the same. If it is not possible to reformat the string, return an empty string "".

Example 1:

Input: s = "aabb" Output: "" Explanation: It is not possible to reformat the string without two adjacent characters being the same.

Example 2:

Input: s = "aaab" Output: "abab" Explanation: It is possible to reformat the string by rearranging the characters as "abab".

Example 3:

Input: s = "leetcode" Output: "leotcede" Explanation: It is possible to reformat the string by rearranging the characters as "leotcede".

The approach to solve this problem is very simple:

• Create a hash table to count the frequency of each character present in the string.
• Find the maximum frequency of a character present in the string.
• If the maximum frequency is greater than half of the string length plus one, return an empty string as it won't be possible to reformat the string.
• Otherwise, initialize two pointers: one to start from the beginning of the string and the other to start from just after the middle of the string.
• Alternate placing the characters from the first half and second half of the string until the string is reformed.

Code:

class Solution { public: string reformat(string s) { unordered_map<char, int> freq; int n = s.length(); for (int i = 0; i < n; i++) { freq[s[i]]++; } int maxFreq = 0; for (auto [c, f] : freq) { maxFreq = max(maxFreq, f); } if (maxFreq > (n + 1) / 2) { return ""; } string res(n, ' '); int i = 0, j = 1; for (auto [c, f] : freq) { while (f > 0 && j < n && i < n) { res[j] = c; j += 2; f--; } while (f > 0 && i < n) { res[i] = c; i += 2; f--; } } return res; } };

Time Complexity:

• O(n) where n is the length of the given string.

Space Complexity:

• O(1) as we are using a hash table of size 26 (number of lowercase letters in the alphabet) that takes constant space.

1