767. Reorganize String
1. Description
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.
2. Example
Example 1:
Input: S = “aab”
Output: “aba”
Example 2:
Input: S = “aaab”
Output: ""
3. Note
- S will consist of lowercase letters and have length in range [1, 500].
4. Solutions
My Accepted Solution
n = m_str.size(), a is abphabet size, but the note says the string will be consist of lowercase letter(26), so we ommit a when computing complexity
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// string reorganizeString(string S)
string reorganizeString(string &m_str)
{
if(m_str.empty()) return m_str;
// store chars occur times
vector<int> charTimes(26, 0); // the note says that the string will be consist of lowercase letter
char mostCommonChar = '\0';
int mostCommonCharTimes = 0;
for(int i = 0; i < m_str.size(); i++)
{
charTimes[m_str[i] - 'a']++;
if(charTimes[m_str[i] - 'a'] > mostCommonCharTimes)
{
mostCommonCharTimes = charTimes[m_str[i] - 'a'];
mostCommonChar = m_str[i];
}
}
// if any char occurs too many times, it is impossible to meet the condition
if(mostCommonCharTimes > (m_str.size()+1) / 2) return string("");
m_str[0] = mostCommonChar;
charTimes[mostCommonChar - 'a']--;
for(int i = 1; i < m_str.size(); i++)
{
// find the char which occurs most times and don't equal to the last char
// so we could try our best to seperate any same chars
char currentChar;
for(int j = 0, times = 0; j < 26; j++)
{
if('a' + j != m_str[i-1] && charTimes[j] > times)
{
times = charTimes[j];
currentChar = 'a' + j;
}
}
m_str[i] = currentChar;
charTimes[currentChar - 'a']--;
}
return m_str;
}
};