Skip to content

2370. Longest Ideal Subsequence 👍

  • Time: $O(n)$
  • Space: $O(26) = O(1)$
 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 {
 public:
  int longestIdealString(string s, int k) {
    // dp[i] := the longest subsequence that ends in ('a' + i)
    vector<int> dp(26);

    for (const char c : s) {
      const int i = c - 'a';
      dp[i] = 1 + getMaxReachable(dp, i, k);
    }

    return ranges::max(dp);
  }

 private:
  int getMaxReachable(const vector<int>& dp, int i, int k) {
    const int first = max(0, i - k);
    const int last = min(25, i + k);
    int maxReachable = 0;
    for (int j = first; j <= last; ++j)
      maxReachable = max(maxReachable, dp[j]);
    return maxReachable;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int longestIdealString(String s, int k) {
    // dp[i] := the longest subsequence that ends in ('a' + i)
    int[] dp = new int[26];

    for (final char c : s.toCharArray()) {
      final int i = c - 'a';
      dp[i] = 1 + getMaxReachable(dp, i, k);
    }

    return Arrays.stream(dp).max().getAsInt();
  }

  private int getMaxReachable(int[] dp, int i, int k) {
    final int first = Math.max(0, i - k);
    final int last = Math.min(25, i + k);
    int maxReachable = 0;
    for (int j = first; j <= last; ++j)
      maxReachable = Math.max(maxReachable, dp[j]);
    return maxReachable;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def longestIdealString(self, s: str, k: int) -> int:
    # dp[i] := the longest subsequence that ends in ('a' + i)
    dp = [0] * 26

    for c in s:
      i = string.ascii_lowercase.index(c)
      dp[i] = 1 + self._getMaxReachable(dp, i, k)

    return max(dp)

  def _getMaxReachable(self, dp: list[int], i: int, k: int) -> int:
    first = max(0, i - k)
    last = min(25, i + k)
    maxReachable = 0
    for j in range(first, last + 1):
      maxReachable = max(maxReachable, dp[j])
    return maxReachable