2370. Longest Ideal Subsequence LeetCode Solution

In this guide, you will get 2370. Longest Ideal Subsequence LeetCode Solution with the best time and space complexity. The solution to Longest Ideal Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Ideal Subsequence solution in C++
Longest Ideal Subsequence solution in Java
Longest Ideal Subsequence solution in Python
Additional Resources

2370. Longest Ideal Subsequence LeetCode Solution image

Problem Statement of Longest Ideal Subsequence

You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied:

t is a subsequence of the string s.
The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.

Return the length of the longest ideal string.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of ‘a’ and ‘z’ is 25, not 1.

Example 1:

Input: s = “acfgbd”, k = 2
Output: 4
Explanation: The longest ideal string is “acbd”. The length of this string is 4, so 4 is returned.
Note that “acfgbd” is not ideal because ‘c’ and ‘f’ have a difference of 3 in alphabet order.
Example 2:

Input: s = “abcd”, k = 3
Output: 4
Explanation: The longest ideal string is “abcd”. The length of this string is 4, so 4 is returned.

Constraints:

1 <= s.length <= 105
0 <= k <= 25
s consists of lowercase English letters.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(26) = O(1)

2370. Longest Ideal Subsequence LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2370. Longest Ideal Subsequence LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2370. Longest Ideal Subsequence LeetCode Solution in Python

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 = ord(c) - ord('a')
      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
 # code by PROGIEZ