Longest Ideal Subsequence
MedPrompt
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:
tis a subsequence of the strings.- The absolute difference in the alphabet order of every two adjacent letters in
tis less than or equal tok.
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 <= 1050 <= k <= 25sconsists 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
dparray of sizen(length ofs) and initialize all its elements to 1. - Initialize
maxLength = 1. - Iterate
ifrom0ton-1. - Inside this loop, iterate
jfrom0toi-1. - If
abs(s.charAt(i) - s.charAt(j)) <= k, updatedp[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.
class Solution { public int longestIdealString(String s, int k) { int n = s.length(); if (n == 0) { return 0; } int[] dp = new int[n]; java.util.Arrays.fill(dp, 1); int maxLength = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (Math.abs(s.charAt(i) - s.charAt(j)) <= k) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } } for (int len : dp) { maxLength = Math.max(maxLength, len); } return maxLength; }}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
Nup to 10^5.
Solutions
Solution
class Solution {public int longestIdealString(String s, int k) { int n = s.length(); int ans = 1; int[] dp = new int[n]; Arrays.fill(dp, 1); Map<Character, Integer> d = new HashMap<>(26); d.put(s.charAt(0), 0); for (int i = 1; i < n; ++i) { char a = s.charAt(i); for (char b = 'a'; b <= 'z'; ++b) { if (Math.abs(a - b) > k) { continue; } if (d.containsKey(b)) { dp[i] = Math.max(dp[i], dp[d.get(b)] + 1); } } d.put(a, i); ans = Math.max(ans, dp[i]); } return ans; }}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.