Skip to main content
Talentd

Longest Ideal Subsequence - Solution & Explanation

MediumHash TableStringDynamic Programming9 min readAsked at: Microsoft, MakeMyTrip
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a string s and an integer k. A subsequence is considered ideal if the absolute difference between the positions of every pair of adjacent characters in the alphabet is at most k. The task is to return the length of the longest such subsequence you can build from s.

This is fundamentally a constrained subsequence problem. You want the longest chain where each new character can only extend subsequences ending with characters within a limited alphabet distance. The constraint ties the problem directly to dynamic programming over characters.

Approach 1: Dynamic Programming with Character Indexing (Time: O(n * 26), Space: O(26))

Track the best subsequence length that ends with each letter of the alphabet. Maintain an array dp[26] where dp[i] stores the longest ideal subsequence ending with character ('a' + i). Iterate through the string and map each character to its alphabet index.

For the current character c, check all characters within the valid range [c - k, c + k]. The maximum value among those entries represents the best subsequence that can be extended. Update dp[c] to max(dp[c], best + 1). Since the alphabet size is fixed at 26, the inner scan is constant time. This keeps the algorithm linear with respect to the string length.

This approach works well because it converts a subsequence dependency into a small state transition over the alphabet. Instead of tracking subsequences for every index, you only store the best result per character. The idea is a classic pattern in string problems that combine ordering constraints with limited character sets.

Approach 2: Optimized Use of HashMap (Time: O(n * 26), Space: O(26))

This variant replaces the fixed array with a HashMap or dictionary keyed by characters. For each character in the string, check all characters whose alphabet distance is within k. Look up their current best subsequence length in the map and compute the best extension.

Update the map entry for the current character with the new maximum length. Conceptually the algorithm is identical to the array approach, but the map structure makes the implementation flexible when the character domain is not strictly limited or when the language favors dictionary-style lookups.

The main operations are hash lookups and updates, which remain constant time on average. This pattern frequently appears in problems involving character transitions and frequency tracking, making it closely related to techniques used in hash table based dynamic programming.

Recommended for interviews: The array-based dynamic programming approach is what most interviewers expect. It shows that you recognize the small fixed alphabet and compress the DP state into 26 buckets instead of tracking every subsequence explicitly. A brute-force subsequence search would be exponential and impractical. The optimized DP demonstrates strong pattern recognition and the ability to reduce a problem to constant-sized state transitions.

Approach 1: Dynamic Programming with Character Indexing

This approach utilizes dynamic programming where we maintain an array "dp" of size 26 (number of alphabets) representing the longest ideal subsequence ending with each character from 'a' to 'z'. The value of dp[char] will be updated by considering the valid preceding characters which are within the range of 'k'. For each character in the string, we update our dp array by iterating over possible characters that are within distance 'k' in the alphabet. The maximum value in the dp array by the end of the iteration gives us the length of the longest ideal subsequence.

The Python code initializes a dp array with 26 elements set to 0. It iterates through each character in the string, calculates its respective index in the dp array, and then checks all indices in the dp that are within a distance 'k'. It updates the dp value at the current character index to be the maximum of the current or the sum of max_len and 1. Finally, it returns the maximum value in the dp array.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1), constant space for dp array.

Try this approach in the editor →

Approach 2: Optimized Use of HashMap

This approach leverages a HashMap to dynamically track the maximum subsequence length for characters encountered in the string, rather than maintaining a fixed size dp array. The HashMap keys represent characters and the values represent the maximum subsequence length possible for the corresponding character. For each character in the string, it checks and updates the longest subsequence length using nearby characters within distance 'k'.

This JavaScript code initializes an array dp of length 26 to keep track of the maximum length of the subsequence that ends with each character. It iterates over each character of the string, calculates its index in dp, and checks all indices that are within k-distance. The dp array is updated with the maximum value found plus one for the current character. The solution is returned as the maximum value in dp array.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Character Indexing

Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1), constant space for dp array.

Optimized Use of HashMap

Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Character IndexingO(n * 26)O(26)Best general solution when the alphabet is fixed (lowercase letters). Fast and memory efficient.
Optimized HashMap ApproachO(n * 26)O(26)Useful when implementing with dynamic character sets or when dictionary lookups are preferred.

Video Solution

Longest Ideal Subsequence - Leetcode 2370 - Python • NeetCodeIO • 13,288 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Ideal Subsequence easy or hard?
Longest Ideal Subsequence is considered a Medium difficulty problem. The challenge is recognizing that the subsequence constraint only depends on alphabet distance, which allows the dynamic programming state to be compressed into just 26 character buckets.
Longest Ideal Subsequence Python/Java solution
Both Python and Java implementations typically use a 26-element array to track the best subsequence length ending with each character. Iterate through the string, compute the valid alphabet range using k, find the maximum dp value in that range, and update the current character entry.
How to solve Longest Ideal Subsequence in O(n)?
Use dynamic programming over alphabet states. Store the best subsequence length for each character in a 26-element array. For each character in the string, check characters within k distance in the alphabet and extend the best subsequence. Since the alphabet size is fixed, each step is constant work, giving near O(n) runtime.
What is the best approach for Longest Ideal Subsequence?
Dynamic programming with character indexing is the most efficient approach. Maintain a 26-length array where each index stores the longest ideal subsequence ending with that character. For each new character, scan the valid alphabet range within distance k and extend the best subsequence. The solution runs in O(n * 26) time with O(26) space.
Is Longest Ideal Subsequence asked at Google/Amazon/Meta?
Problems involving constrained subsequences and dynamic programming over characters appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of this pattern test your ability to optimize DP state using small fixed domains such as the alphabet.
What data structure is used in Longest Ideal Subsequence?
The core data structure is a dynamic programming table indexed by character. Most implementations use a fixed array of size 26, while some versions use a HashMap or dictionary to track the best subsequence length ending with each character.
What is the time complexity of Longest Ideal Subsequence?
The optimal algorithm runs in O(n * 26) time, where n is the length of the string. For every character you scan at most 26 possible alphabet states to find the best extension. Because the alphabet size is constant, the runtime behaves like O(n) in practice.

Ready to solve this problem?

Practice Longest Ideal Subsequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Increasing Subsequence