字符消消乐

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

思路

使用栈数据结构，碰到左括号就压入右括号，碰到右括号就比较，相同则弹出，不同则结束程序。

Use a stack of characters.

When you encounter an opening bracket, push it to the top of the stack.

When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.

C++解法

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

时间复杂度: O(n)

空间复杂度: O(n)

下面的写法是错误的：

class Solution {
public:
    bool isValid(string s) {
        if(s.size() % 2 != 0) return false;
        stack<char> st;
        for(char ch : s){
            if(ch == '('){
                st.push(')');
            }else if(ch == '['){
                st.push(']');
            }else if(ch == '{'){
                st.push('}');
            }else{
                if(st.top() == ch){
                    st.pop();
                }else{
                    return false;
                }
            }
        }
        return st.empty();
    }
};

其中的if(st.top() == ch)会报错。

Java解法

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}

1047. Remove All Adjacent Duplicates In String

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

思路

本题也是用栈来解决的经典题目。

那么栈里应该放的是什么元素呢？

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

然后再去做对应的消除操作。 如动画所示：

1047.删除字符串中的所有相邻重复项

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

C++解法

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

当然可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

代码如下：

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)，返回值不计空间复杂度

Java解法

使用 Deque 作为堆栈

class Solution {
    public String removeDuplicates(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

拿字符串直接作为栈，省去了栈还要转为字符串的操作。

class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top >= 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

拓展：双指针

class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}

Python解法

# 方法一，使用栈
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)  # 字符串拼接

# 方法二，使用双指针模拟栈，如果不让用栈可以作为备选方法。
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        slow = fast = 0
        length = len(res)

        while fast < length:
            # 如果一样直接换，不一样会把后面的填在slow的位置
            res[slow] = res[fast]
            
            # 如果发现和前一个一样，就退一格指针
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
            
        return ''.join(res[0: slow])

Go解法

使用栈

func removeDuplicates(s string) string {
    stack := make([]rune, 0)
    for _, val := range s {
        if len(stack) == 0 || val != stack[len(stack)-1] {
            stack = append(stack, val)
        } else {
            stack = stack[:len(stack)-1]
        }
    }
    var res []rune
    for len(stack) != 0 { // 将栈中元素放到result字符串汇总
        res = append(res, stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    // 此时字符串需要反转一下
    l, r := 0, len(res)-1
    for l < r {
        res[l], res[r] = res[r], res[l]
        l++
        r--
    }
    return string(res)
}

拿字符串直接作为栈，省去了栈还要转为字符串的操作

func removeDuplicates(s string) string {
    var stack []byte
    for i := 0; i < len(s);i++ {
        // 栈不空 且 与栈顶元素不等
        if len(stack) > 0 && stack[len(stack)-1] == s[i] {
            // 弹出栈顶元素 并 忽略当前元素(s[i])
            stack = stack[:len(stack)-1]
        }else{
            // 入栈
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

1209. Remove All Adjacent Duplicates in String II

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

  • 1 <= s.length <= 10^5
  • 2 <= k <= 10^4
  • s only contains lowercase English letters.

思路

Solution 1: Two Pointers

Solution 2: Stack

Save the character c and its count to the stack.
If the next character c is same as the last one, increment the count.
Otherwise push a pair (c, 1) into the stack.
I used a dummy element ('#', 0) to avoid empty stack.

Complexity

Time O(N) for one pass

Space O(N)

C++解法

    string removeDuplicates(string s, int k) {
        int i = 0, n = s.length();
        vector<int> count(n);
        for (int j = 0; j < n; ++j, ++i) {
            s[i] = s[j];
            count[i] = i > 0 && s[i - 1] == s[j] ? count[i - 1] + 1 : 1;
            if (count[i] == k) i -= k;
        }
        return s.substr(0, i);
    }

    string removeDuplicates(string s, int k) {
        vector<pair<int, char>> stack = {{0, '#'}};
        for (char c: s) {
            if (stack.back().second != c) {
                stack.push_back({1, c});
            } else if (++stack.back().first == k)
                stack.pop_back();
        }
        string res;
        for (auto & p : stack) {
            res.append(p.first, p.second);
        }
        return res;
    }

Java解法

    public String removeDuplicates(String s, int k) {
        int[] count = new int[s.length()];
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()) {
            sb.append(c);
            int last = sb.length()-1;
            count[last] = 1 + (last > 0 && sb.charAt(last) == sb.charAt(last-1) ? count[last-1] : 0);
            if(count[last] >= k) sb.delete(sb.length()-k, sb.length());
        }
        return sb.toString();
    }

    public String removeDuplicates(String s, int k) {
        int i = 0, n = s.length(), count[] = new int[n];
        char[] stack = s.toCharArray();
        for (int j = 0; j < n; ++j, ++i) {
            stack[i] = stack[j];
            count[i] = i > 0 && stack[i - 1] == stack[j] ? count[i - 1] + 1 : 1;
            if (count[i] == k) i -= k;
        }
        return new String(stack, 0, i);
    }

Python解法

    def removeDuplicates(self, s, k):
        stack = [['#', 0]]
        for c in s:
            if stack[-1][0] == c:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([c, 1])
        return ''.join(c * k for c, k in stack)

2390. Removing Stars From a String

You are given a string s, which contains stars *.

In one operation, you can:

  • Choose a star in s.
  • Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

  • The input will be generated such that the operation is always possible.
  • It can be shown that the resulting string will always be unique.

Example 1:

Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:

  • The closest character to the 1st star is 't' in "lee**t****cod*e". s becomes "lee*cod*e".
  • The closest character to the 2nd star is 'e' in "le**e***cod*e". s becomes "lecod*e".
  • The closest character to the 3rd star is 'd' in "leco**d***e". s becomes "lecoe". There are no more stars, so we return "lecoe".

Example 2:

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters and stars *.
  • The operation above can be performed on s.

思路

What data structure could we use to efficiently perform these removals?

Use a stack to store the characters. Pop one character off the stack at each star. Otherwise, we push the character onto the stack.

当然可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

C++解法

class Solution {
public:
    string removeStars(string s) {
        string result;
        for(char ch : s) {
            if(result.empty() || ch != '*') {
                result.push_back(ch);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

2716. Minimize String Length

Given a string s, you have two types of operation:

  1. Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the left of i (if exists).
  2. Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the right of i (if exists).

Your task is to minimize the length of s by performing the above operations zero or more times.

Return an integer denoting the length of the minimized string.

Example 1:

Input: s = "aaabc"

Output: 3

Explanation:

  1. Operation 2: we choose i = 1 so c is 'a', then we remove s[2] as it is closest 'a' character to the right of s[1].
    s becomes "aabc" after this.
  2. Operation 1: we choose i = 1 so c is 'a', then we remove s[0] as it is closest 'a' character to the left of s[1].
    s becomes "abc" after this.

Example 2:

Input: s = "cbbd"

Output: 3

Explanation:

  1. Operation 1: we choose i = 2 so c is 'b', then we remove s[1] as it is closest 'b' character to the left of s[1].
    s becomes "cbd" after this.

Example 3:

Input: s = "baadccab"

Output: 4

Explanation:

  1. Operation 1: we choose i = 6 so c is 'a', then we remove s[2] as it is closest 'a' character to the left of s[6].
    s becomes "badccab" after this.
  2. Operation 2: we choose i = 0 so c is 'b', then we remove s[6] as it is closest 'b' character to the right of s[0].
    s becomes "badcca" fter this.
  3. Operation 2: we choose i = 3 so c is 'c', then we remove s[4] as it is closest 'c' character to the right of s[3].
    s becomes "badca" after this.
  4. Operation 1: we choose i = 4 so c is 'a', then we remove s[1] as it is closest 'a' character to the left of s[4].
    s becomes "bdca" after this.

Constraints:

  • 1 <= s.length <= 100
  • s contains only lowercase English letters

思路

The minimized string will not contain duplicate characters.

The minimized string will contain all distinct characters of the original string.

C++解法

class Solution {
public:
    int minimizedStringLength(string s) {
        return unordered_set<char>(s.begin(), s.end()).size();
    }
};

使用hash数组求解：

class Solution {
public:
    int minimizedStringLength(string s) {
        int hash[26] = {0};
        for(char ch : s){
            hash[ch - 'a']++;
        }
        int count = 0;
        for(int i = 0; i < 26; i++){
            if(hash[i] != 0){
                count++;
            }
        }
        return count;
    }
};

注意：int hash[26] = {0};这行代码确保 hash 数组的所有元素都被初始化为零，避免了使用未初始化值的问题。

Java解法

class Solution {
    public int minimizedStringLength(String s) {
        return (int) s.chars().distinct().count();
    }
}

Python3解法

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return len(set(s))