#2370

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Ideal Subsequence

The Longest Ideal Subsequence problem involves finding the longest subsequence where each character has a difference of at most k in alphabetical order.

hash table string dynamic programming

Problem Statement

You are given a string s consisting of lowercase letters and an integer k. A subsequence is a sequence derived from s by deleting some characters without changing the order of the remaining characters. You need to find the length of the longest subsequence in s such that for every pair of consecutive characters in the subsequence, their alphabetic difference is at most k.

For example, in the string "acfgbd" and k = 2, the longest ideal subsequence is "acbd", which has a length of 4. The string "acfgbd" itself is not ideal because 'c' and 'f' have an alphabetic difference of 3, which is greater than k.

Examples

Example 1

Input: s = "acfgbd", k = 2

Output: 4

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

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.

Solution Approach

Dynamic Programming with State Transition

To solve this problem efficiently, use dynamic programming (DP) with state transition. Create an array dp where dp[i] represents the length of the longest ideal subsequence ending at index i. For each character s[i], iterate through previous characters and check if their alphabetic difference is at most k, then update dp[i].

Optimizing with Hash Map

To avoid a time complexity of O(N^2), use a hash map to store the longest subsequences ending with specific characters. This reduces unnecessary comparisons and ensures each state transition is handled in constant time.

Iterating Over String

Start iterating through the string from left to right, updating the DP array by checking the conditions for ideal subsequences. Ensure you track the longest subsequence efficiently by using the hash map to look up the best possible transitions.

Complexity Analysis

Metric	Value
Time	O(NL)
Space	O(L)

The time complexity of this solution is O(N * L), where N is the length of the string and L is the number of distinct characters (26 for lowercase letters). The space complexity is O(L), as we store only the necessary states in the hash map for each character.

What Interviewers Usually Probe

The candidate correctly applies dynamic programming to solve the problem by defining an optimal state transition.
The candidate uses a hash map efficiently to store and retrieve subsequence lengths, reducing time complexity.
The candidate demonstrates a clear understanding of subsequence problems, especially the constraints defined by the alphabetic difference k.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by using a hash map can lead to O(N^2) time complexity, which is inefficient for large strings.
Not correctly tracking the transitions between subsequences may result in incorrect or suboptimal solutions.
The candidate might not consider edge cases such as the minimum or maximum values of k, or strings with a single character.

Follow-up variants

Consider variants where the string contains uppercase letters, expanding the alphabetic range.
Modify the problem to allow only a fixed number of deletions, adding a layer of complexity.
Test the solution with varying k values to examine how it handles different constraints in the problem.

FAQ

What is the main pattern used to solve the Longest Ideal Subsequence problem?

The main pattern is state transition dynamic programming, where the solution relies on transitioning through states efficiently, often using a hash map.

How does dynamic programming apply to the Longest Ideal Subsequence problem?

Dynamic programming helps by storing the lengths of the longest subsequences ending at each character in the string, allowing for optimal transitions based on the alphabetic difference condition.

What is the time complexity of the Longest Ideal Subsequence problem?

The time complexity is O(N * L), where N is the length of the string and L is the number of distinct characters (26 for lowercase English letters).

Can we solve the Longest Ideal Subsequence problem without using dynamic programming?

While it's possible, using dynamic programming is the most efficient approach. A brute-force solution would have a time complexity of O(N^2), which is not scalable for large inputs.

How does using a hash map improve the solution for this problem?

Using a hash map allows for faster lookup and update of the longest subsequences ending with specific characters, reducing the need for nested loops and improving time complexity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    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)

Continue Practicing

#2266 count number of texts #2262 total appeal of a string #2606 find the substring with maximum cost