1544. 整理字符串

🟢   🔖  栈 字符串  🔗 力扣 LeetCode

题目

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

A good string is a string which doesn't have two adjacent characterss[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.

题目大意

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要满足如下条件:

• 若 s[i] 是小写字符，则 s[i+1] 不可以是相同的大写字符。
• 若 s[i] 是大写字符，则 s[i+1] 不可以是相同的小写字符。

请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意： 空字符串也属于整理好的字符串，尽管其中没有任何字符。

示例 1：

输入： s = "leEeetcode"

输出： "leetcode"

解释： 无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。

示例 2：

输入： s = "abBAcC"

输出： ""

解释： 存在多种不同情况，但所有的情况都会导致相同的结果。例如：

"abBAcC" --> "aAcC" --> "cC" --> ""

"abBAcC" --> "abBA" --> "aA" --> ""

示例 3：

输入： s = "s"

输出： "s"

提示：

• 1 <= s.length <= 100
• s 只包含小写和大写英文字母

解题思路

我们可以用 栈 来解决这个问题。

1. 遍历字符串中的每个字符：

   • 如果栈顶元素和当前字符形成一个大小写匹配对（ASCII 差值为 32），则从栈中移除栈顶元素。
   • 否则，将当前字符压入栈中。

2. 遍历结束后，栈中的字符构成了最终的字符串，将其转换为字符串返回。

复杂度分析

• 时间复杂度：O(n)，遍历字符串，每个字符最多被压入和弹出栈一次。
• 空间复杂度：O(n)，最坏情况下栈中存储所有字符。

代码

/**
 * @param {string} s
 * @return {string}
 */
/**
 * @param {string} s
 * @return {string}
 */
var makeGood = function (s) {
	let stack = [];
	for (let char of s) {
		// 检查是否存在相邻的大写/小写字符
		if (
			stack.length > 0 &&
			Math.abs(char.charCodeAt() - stack[stack.length - 1].charCodeAt()) === 32
		) {
			stack.pop(); // 移除大小写匹配的字符
		} else {
			stack.push(char); // 压入当前字符
		}
	}
	return stack.join('');
};