Skip to content

3561. Resulting String After Adjacent Removals

Description

You are given a string s consisting of lowercase English letters.

You must repeatedly perform the following operation while the string s has at least two consecutive characters:

  • Remove the leftmost pair of adjacent characters in the string that are consecutive in the alphabet, in either order (e.g., 'a' and 'b', or 'b' and 'a').
  • Shift the remaining characters to the left to fill the gap.

Return the resulting string after no more operations can be performed.

Note: Consider the alphabet as circular, thus 'a' and 'z' are consecutive.

 

Example 1:

Input: s = "abc"

Output: "c"

Explanation:

  • Remove "ab" from the string, leaving "c" as the remaining string.
  • No further operations are possible. Thus, the resulting string after all possible removals is "c".

Example 2:

Input: s = "adcb"

Output: ""

Explanation:

  • Remove "dc" from the string, leaving "ab" as the remaining string.
  • Remove "ab" from the string, leaving "" as the remaining string.
  • No further operations are possible. Thus, the resulting string after all possible removals is "".

Example 3:

Input: s = "zadb"

Output: "db"

Explanation:

  • Remove "za" from the string, leaving "db" as the remaining string.
  • No further operations are possible. Thus, the resulting string after all possible removals is "db".

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.

Solutions

Solution 1: Stack

We can use a stack to simulate the process of removing adjacent characters. Iterate through each character in the string. If the character at the top of the stack and the current character are consecutive (i.e., their ASCII values differ by 1 or 25), pop the top character from the stack; otherwise, push the current character onto the stack. Finally, the characters remaining in the stack are those that can no longer be removed. Join the characters in the stack into a string and return it.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string.

1
2
3
4
5
6
7
8
9
class Solution:
    def resultingString(self, s: str) -> str:
        stk = []
        for c in s:
            if stk and abs(ord(c) - ord(stk[-1])) in (1, 25):
                stk.pop()
            else:
                stk.append(c)
        return "".join(stk)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public String resultingString(String s) {
        StringBuilder stk = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (stk.length() > 0 && isContiguous(stk.charAt(stk.length() - 1), c)) {
                stk.deleteCharAt(stk.length() - 1);
            } else {
                stk.append(c);
            }
        }
        return stk.toString();
    }

    private boolean isContiguous(char a, char b) {
        int t = Math.abs(a - b);
        return t == 1 || t == 25;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    string resultingString(string s) {
        string stk;
        for (char c : s) {
            if (stk.size() && (abs(stk.back() - c) == 1 || abs(stk.back() - c) == 25)) {
                stk.pop_back();
            } else {
                stk.push_back(c);
            }
        }
        return stk;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func resultingString(s string) string {
    isContiguous := func(a, b rune) bool {
        x := abs(int(a - b))
        return x == 1 || x == 25
    }
    stk := []rune{}
    for _, c := range s {
        if len(stk) > 0 && isContiguous(stk[len(stk)-1], c) {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, c)
        }
    }
    return string(stk)
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function resultingString(s: string): string {
    const stk: string[] = [];
    const isContiguous = (a: string, b: string): boolean => {
        const x = Math.abs(a.charCodeAt(0) - b.charCodeAt(0));
        return x === 1 || x === 25;
    };
    for (const c of s) {
        if (stk.length && isContiguous(stk.at(-1)!, c)) {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.join('');
}

Comments