Longest Ideal Subsequence

Med

#2158Time: O(N^2), where `N` is the length of the string `s`. The nested loops lead to a quadratic time complexity.Space: O(N) to store the `dp` array, where N is the length of the string.1 company

Patterns

Dynamic Programming

Data structures

Hash Table String

Companies

MakeMyTrip

Prompt

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 <= 10⁵
0 <= k <= 25
s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i] as the length of the longest ideal subsequence that ends with the character s[i]. To compute dp[i], we iterate through all previous characters s[j] (where j < i). If s[j] can precede s[i] in an ideal subsequence (i.e., abs(s[i] - s[j]) <= k), we can potentially extend the subsequence ending at j. Therefore, dp[i] is 1 plus the maximum dp[j] over all valid j.

Algorithm

Create a dp array of size n (length of s) and initialize all its elements to 1.
Initialize maxLength = 1.
Iterate i from 0 to n-1.
Inside this loop, iterate j from 0 to i-1.
If abs(s.charAt(i) - s.charAt(j)) <= k, update dp[i] = max(dp[i], 1 + dp[j]).
After the inner loop, update maxLength = max(maxLength, dp[i]).
Return maxLength.

Walkthrough

We create a DP array, dp, of the same size as the input string s. dp[i] will store the length of the longest ideal subsequence ending at index i. We initialize every element of dp to 1, as any single character is an ideal subsequence of length 1. We then iterate through the string s from the first character (i = 0) to the end. For each character s[i], we perform an inner loop from the beginning of the string up to i-1 (j = 0 to i-1). Inside the inner loop, we check if the absolute difference between the alphabet order of s[i] and s[j] is less than or equal to k. If the condition abs(s.charAt(i) - s.charAt(j)) <= k is met, it means we can append s[i] to an ideal subsequence ending with s[j]. We update dp[i] with the maximum of its current value and 1 + dp[j]. After iterating through all j < i, dp[i] will hold the length of the longest ideal subsequence ending at s[i]. The final answer is the maximum value found in the dp array after the loops complete.

1class Solution {2    public int longestIdealString(String s, int k) {3        int n = s.length();4        if (n == 0) {5            return 0;6        }7        int[] dp = new int[n];8        java.util.Arrays.fill(dp, 1);9        int maxLength = 0;10 11        for (int i = 0; i < n; i++) {12            for (int j = 0; j < i; j++) {13                if (Math.abs(s.charAt(i) - s.charAt(j)) <= k) {14                    dp[i] = Math.max(dp[i], 1 + dp[j]);15                }16            }17        }18        19        for (int len : dp) {20            maxLength = Math.max(maxLength, len);21        }22        23        return maxLength;24    }25}

Complexity

Time

O(N^2), where `N` is the length of the string `s`. The nested loops lead to a quadratic time complexity.

Space

O(N) to store the `dp` array, where N is the length of the string.

Trade-offs

Pros

Relatively simple to understand and implement.
Correctly solves the problem for smaller inputs.

Cons

Inefficient for large inputs. It will result in a "Time Limit Exceeded" error for N up to 10^5.

This approach improves upon the brute-force DP by changing the state definition. Instead of tracking the length of subsequences ending at each index, we track the length of the longest ideal subsequence ending with each possible character ('a' through 'z'). Since there are only 26 lowercase letters, our DP table size becomes constant.

Algorithm

Create an integer array dp of size 26, initialized to all zeros.
Initialize result = 0.
Iterate through each character c in the string s.
For each c, determine its index charIndex = c - 'a'.
Find the range of previous character indices to check: start = max(0, charIndex - k) and end = min(25, charIndex + k).
Find maxPrevLength by iterating from start to end and finding the maximum value in dp within that range.
Update dp[charIndex] = maxPrevLength + 1.
Update result = max(result, dp[charIndex]).
After the loop, return result.

Walkthrough

The key observation is that to find the length of the longest ideal subsequence ending with the current character c, we only need to know the lengths of the longest ideal subsequences ending with characters "close" to c. The exact positions of these previous characters in the string s do not matter, only that they appeared before the current character. We use a DP array, let's call it dp, of size 26. dp[i] will store the length of the longest ideal subsequence seen so far that ends with the character corresponding to index i (i.e., 'a' + i). We iterate through the input string s one character at a time. For the current character c, we need to find the longest ideal subsequence we can extend. The previous character, p, must satisfy abs(c - p) <= k. We search for the maximum length among all valid previous characters. This means checking dp for all characters p in the range [c - k, c + k]. Let maxPrevLength be this maximum value. The length of the new longest ideal subsequence ending with c is 1 + maxPrevLength. We update dp[c - 'a'] with this new length. We also keep track of the overall maximum length found so far. After processing all characters in s, this overall maximum is our answer.

1class Solution {2    public int longestIdealString(String s, int k) {3        // dp[i] stores the longest ideal subsequence ending with char 'a' + i4        int[] dp = new int[26]; 5        int result = 0;6 7        for (char c : s.toCharArray()) {8            int charIndex = c - 'a';9            int maxPrevLength = 0;10            11            // Find the max length of a subsequence ending with a character12            // within k distance of the current character.13            int start = Math.max(0, charIndex - k);14            int end = Math.min(25, charIndex + k);15            16            for (int j = start; j <= end; j++) {17                maxPrevLength = Math.max(maxPrevLength, dp[j]);18            }19            20            // Update the length for the current character21            dp[charIndex] = maxPrevLength + 1;22            23            // Update the overall result24            result = Math.max(result, dp[charIndex]);25        }26        27        return result;28    }29}

Complexity

Time

O(N * C), where `N` is the length of the string `s` and `C` is the size of the character set (26). Since `C` is constant, the complexity is effectively O(N).

Space

O(C) or O(1), where C is the size of the character set (26). The space required for the `dp` array is constant and does not depend on the input string length.

Trade-offs

Pros

Highly efficient and passes the given constraints.
Linear time complexity is optimal for this problem as we must scan the entire string at least once.

Cons

The logic is slightly more complex than the brute-force approach.

Solutions

Solution

1class Solution {2public3  int longestIdealString(String s, int k) {4    int n = s.length();5    int ans = 1;6    int[] dp = new int[n];7    Arrays.fill(dp, 1);8    Map<Character, Integer> d = new HashMap<>(26);9    d.put(s.charAt(0), 0);10    for (int i = 1; i < n; ++i) {11      char a = s.charAt(i);12      for (char b = 'a'; b <= 'z'; ++b) {13        if (Math.abs(a - b) > k) {14          continue;15        }16        if (d.containsKey(b)) {17          dp[i] = Math.max(dp[i], dp[d.get(b)] + 1);18        }19      }20      d.put(a, i);21      ans = Math.max(ans, dp[i]);22    }23    return ans;24  }25}

1class Solution {2public:3  int longestIdealString(string s, int k) {4    int n = s.size();5    int ans = 1;6    vector<int> dp(n, 1);7    unordered_map<char, int> d;8    d[s[0]] = 0;9    for (int i = 1; i < n; ++i) {10      char a = s[i];11      for (char b = 'a'; b <= 'z'; ++b) {12        if (abs(a - b) > k)13          continue;14        if (d.count(b))15          dp[i] = max(dp[i], dp[d[b]] + 1);16      }17      d[a] = i;18      ans = max(ans, dp[i]);19    }20    return ans;21  }22};

1class Solution:2    def longestIdealString(self, s: str, k: int) -> int: n = len(s) ans = 1 dp = [1] * n d = {s[0]: 0} for i in range(1, n): a = ord(s[i]) for b in ascii_lowercase: if abs(a - ord(b)) > k: continue if b in d: dp[i] = max(dp[i], dp[d[b]] + 1) d[s[i]] = i return max(dp)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem