Question

1544. Make The String Great

中文文档

Description

Given a string s of lower and upper case English letters.

A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:

• 0 <= i <= s.length - 2
• s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return _the string_ after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

 

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

 

Constraints:

• 1 <= s.length <= 100
• s contains only lower and upper case English letters.

Solutions

Solution 1

class Solution:
  def makeGood(self, s: str) -> str:
    stk = []
    for c in s:
      if not stk or abs(ord(stk[-1]) - ord(c)) != 32:
        stk.append(c)
      else:
        stk.pop()
    return "".join(stk)

class Solution {
  public String makeGood(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (sb.length() == 0 || Math.abs(sb.charAt(sb.length() - 1) - c) != 32) {
        sb.append(c);
      } else {
        sb.deleteCharAt(sb.length() - 1);
      }
    }
    return sb.toString();
  }
}

class Solution {
public:
  string makeGood(string s) {
    string stk;
    for (char c : s) {
      if (stk.empty() || abs(stk.back() - c) != 32) {
        stk += c;
      } else {
        stk.pop_back();
      }
    }
    return stk;
  }
};

func makeGood(s string) string {
  stk := []rune{}
  for _, c := range s {
    if len(stk) == 0 || abs(int(stk[len(stk)-1]-c)) != 32 {
      stk = append(stk, c)
    } else {
      stk = stk[:len(stk)-1]
    }
  }
  return string(stk)
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}