This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1047 on LeetCode. Remove all contiguous duplicates in a string. The difficulty is simple.

Tag: “queue”, “simulation”

Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

Example:

Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca", we can delete "bb" because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", where only "aa" can be deduplicated, so the final string is "ca".Copy the code

Tip:

  • 1 <= S.length <= 20000
  • The “S” is a lowercase letter only.

Stack solution

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        Deque<Character> d = new ArrayDeque<>();
        for (char c : cs) {
            if(! d.isEmpty() && d.peekLast().equals(c)) { d.pollLast(); }else {
                d.addLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(! d.isEmpty()) sb.append(d.pollLast()); sb.reverse();returnsb.toString(); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Stack solution (array simulation)

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        char[] d = new char[s.length()];
        int hh = 0, tt = -1;
        for (char c : cs) {
            if (hh <= tt && d[tt] == c) {
                tt--;
            } else {
                d[++tt] = c;
            }
        }  
        StringBuilder sb = new StringBuilder();
        while (hh <= tt) sb.append(d[tt--]);
        sb.reverse();
        returnsb.toString(); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Double – ended queue solution

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        Deque<Character> d = new ArrayDeque<>();
        for (char c : cs) {
            if(! d.isEmpty() && d.peekLast().equals(c)) { d.pollLast(); }else {
                d.addLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(! d.isEmpty()) sb.append(d.pollFirst());returnsb.toString(); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

(array simulation) double – ended queue solution

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        char[] d = new char[s.length()];
        int hh = 0, tt = -1;
        for (char c : cs) {
            if (hh <= tt && d[tt] == c) {
                tt--;
            } else {
                d[++tt] = c;
            }
        }  
        StringBuilder sb = new StringBuilder();
        while (hh <= tt) sb.append(d[hh++]);
        returnsb.toString(); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Pure array solution

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        char[] d = new char[s.length()];
        int hh = 0, tt = -1;
        for (char c : cs) {
            if (hh <= tt && d[tt] == c) {
                tt--;
            } else{ d[++tt] = c; }}return new String(d, 0, tt + 1); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.1047 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.