Skip to content

3563. Lexicographically Smallest String After Adjacent Removals 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  string lexicographicallySmallestString(string s) {
    const int n = s.size();
    // dp[i][j] := the lexicographically smallest string by removing adjacent
    // letters from s[i..j)
    vector<vector<string>> dp(n + 1, vector<string>(n + 1));

    for (int d = 1; d <= n; ++d)
      for (int i = 0; i + d <= n; ++i) {
        const int j = i + d;
        // 1. Keep s[i].
        string minString = s[i] + dp[i + 1][j];
        // 2. Remove s[i] and s[k] if possible.
        for (int k = i + 1; k < j; ++k)
          if (isConsecutive(s[i], s[k]) && dp[i + 1][k].empty())
            minString = min(minString, dp[k + 1][j]);
        dp[i][j] = minString;
      }

    return dp[0][n];
  }

 private:
  bool isConsecutive(char a, char b) {
    return abs(a - b) == 1 || abs(a - b) == 25;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public String lexicographicallySmallestString(String s) {
    final int n = s.length();
    // dp[i][j]: the lexicographically smallest string by removing adjacent letters from s[i..j)
    String[][] dp = new String[n + 1][n + 1];

    // Initialize dp[i][i] = "" for all i.
    for (int i = 0; i <= n; ++i)
      dp[i][i] = "";

    for (int d = 1; d <= n; ++d)
      for (int i = 0; i + d <= n; ++i) {
        final int j = i + d;
        // 1. Keep s[i].
        String minString = s.charAt(i) + dp[i + 1][j];
        // 2. Remove s[i] and s[k] if possible.
        for (int k = i + 1; k < j; ++k)
          if (isConsecutive(s.charAt(i), s.charAt(k)) && dp[i + 1][k].isEmpty()) {
            final String candidate = dp[k + 1][j];
            if (candidate.compareTo(minString) < 0)
              minString = candidate;
          }
        dp[i][j] = minString;
      }

    return dp[0][n];
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def lexicographicallySmallestString(self, s: str) -> str:
    n = len(s)
    # dp[i][j]: the lexicographically smallest string by removing adjacent
    # letters from s[i..j)
    dp = [[''] * (n + 1) for _ in range(n + 1)]

    for d in range(1, n + 1):
      for i in range(n - d + 1):
        j = i + d
        # 1. Keep s[i].
        minString = s[i] + dp[i + 1][j]
        # 2. Remove s[i] and s[k] if possible.
        for k in range(i + 1, j):
          if self._isConsecutive(s[i], s[k]) and dp[i + 1][k] == '':
            candidate = dp[k + 1][j]
            if candidate < minString:
              minString = candidate
        dp[i][j] = minString

    return dp[0][n]

  def _isConsecutive(self, a: str, b: str) -> bool:
    return abs(ord(a) - ord(b)) == 1 or abs(ord(a) - ord(b)) == 25