Collating strings

1544. Sorting strings

The difficulty is simple 46

Give you a string of uppercase and lowercase English letters s .

In a sorted string , Two adjacent characters s[i] and s[i+1], among 0<= i <= s.length-2 , The following conditions must be met :

• if s[i] Is a lowercase character , be s[i+1] Cannot be the same uppercase character .
• if s[i] Is an uppercase character , be s[i+1] Lowercase characters can be different .

Please arrange the strings , Each time you can choose from the string that meets the above conditions Two adjacent Character and delete , Until the string is sorted .

Please return to the sorted character string . The problem is guaranteed under the given constraints , The answer corresponding to the test sample is unique .

** Be careful ：** Empty strings are also sorted strings , Although there are no characters in it .

Example 1：

 Input ：s = "leEeetcode"
 Output ："leetcode"
 explain ： Whether you choose... For the first time  i = 1  still  i = 2, Will make  "leEeetcode"  Reduced to  "leetcode" .

Example 2：

 Input ：s = "abBAcC"
 Output ：""
 explain ： There are many different situations , But all situations lead to the same result . for example ：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3：

 Input ：s = "s"
 Output ："s"

Tips ：

• 1 <= s.length <= 100
• s Only lowercase and uppercase letters

---

Train of thought ：【 Stack 】

Using the idea of stacks , Create a new string **tmp ** Used to store the characters to be compared , First of all s First character of push_back To tmp in , Then on s Start traversing other characters in , Then there will be the following two situations ：

• If tmp Top of stack , That is to say tmp The end of the string is A lowercase letter Words , be s[ i ] Cannot be uppercase of the same character , If so, then tmp The trailing element of the string pop fall .
• If tmp Top of stack , That is to say tmp The end of the string is Capitalization Words , be s[ i ] Cannot be lowercase of the same character , If so, then tmp The trailing element of the string pop fall .

class Solution {
    
public:
    string makeGood(string s) {
    
        string tmp;
        tmp.push_back(s[0]);  // take s The first element of push To tmp Tail of 
        for(int i = 1; i < s.size(); ++i)
        {
    
             if(s[i] + 32 == tmp.back() || s[i] - 32 == tmp.back())
             {
    
                 tmp.pop_back();
             }
             else
             {
    
                 tmp += s[i];
             }
        }
        return tmp;
    }
};

Train of thought two ： Direct traversal

Take it directly s[ i ] And s[ i + 1 ] Compare , If the same case occurs , Then the elements in these two positions are directly erase fall , Then go back to the beginning of the string to traverse . The time complexity of this method is relatively high .

class Solution {
    
public:
    string makeGood(string s) {
    
        int n = s.size();
        int i = 0;
        while(i < n - 1)
        {
    
            if(s[i] >= 'a' && s[i] <= 'z')
            {
    
                if((s[i] - 32) == s[i+1])
                {
    
                    s.erase(i, 2);
                    i = 0;
                    continue;
                }
            }
            else
            {
    
                if((s[i] + 32) == s[i+1])
                {
    
                    s.erase(i, 2);
                    i = 0;
                    continue;
                }
            }
            ++i;
        }
        return s;
    }
};