2370. Longest Ideal Subsequence

Problem Description

The LeetCode problem presented asks us to find the length of the longest ideal subsequence from a given string s. An ideal subsequence is one that satisfies two conditions. First, it must be a subsequence of s, which means it can be formed by removing some or no characters from s without changing the order of the remaining characters. Second, for every pair of adjacent letters in this subsequence, the absolute difference in their alphabetical order must be less than or equal to a given integer k.

To explain further, a subsequence is different from a substring since a substring is contiguous and appears in the same order within the original string, whereas a subsequence is not required to be contiguous but must appear in the same relative order.

The problem statement also clarifies that the alphabetical order difference isn't cyclic, meaning that the difference between a and z is considered to be 25, not 1.

Intuition

To solve this problem, we can use dynamic programming, which involves breaking the problem into smaller subproblems and solving each subproblem just once, storing the solution in a table for easy access when solving subsequent subproblems.

The intuition behind the approach is to consider each character in the string s one by one and determine the length of the longest ideal subsequence ending with that character. For each character, we need to find the previous character in the subsequence that can be connected to it (based on the condition about the alphabetical difference) for which the subsequence length is the longest possible.

We create a dictionary d that keeps track of the last occurrence index for each character that can be a candidate for forming a subsequence. We also maintain an array dp where dp[i] represents the length of the longest ideal subsequence ending at s[i].

For each character s[i] in the string, we iterate over every lowercase letter and check if it can form a sequence with s[i], satisfying the absolute difference condition. If it's a valid character, we update dp[i] to the maximum of its current value or 1 plus the length of the subsequence ending with the valid character found in our dictionary d. By doing this iteratively, we build upon the solutions of the subproblems until we reach the end of the string. Finally, the answer is the maximum value in the dp array, which represents the length of the longest ideal subsequence we can obtain from s.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution provided follows the dynamic programming approach to tackle the problem of finding the longest ideal subsequence.

Firstly, we initialize an array dp with all elements as 1, because the minimum length of an ideal subsequence that can end at any character is at least 1 – the character itself. We also create a dictionary d to keep track of the last index where each character occurred while checking the sequence.

The core of the solution code is a nested loop. The outer loop iterates through the string s, and the inner loop iterates through all lowercase ASCII letters to check whether they can form an ideal subsequence with the current character s[i]. Here's a breakdown of each element of the code:

• n = len(s): We determine the length of the given string s.
• dp = [1] * n: Creates a list dp with n elements, all initialized to 1.
• d = {s[0]: 0}: Initializes the dictionary d with the first character of the string s as the key and 0 as its index.
• for i in range(1, n): Outer loop to traverse the string s starting from index 1 since index 0 is used for initialization.
• a = ord(s[i]): Converts the current character s[i] to its ASCII value to facilitate comparison based on alphabetical order.
• Inside the outer loop is an inner loop: for b in ascii_lowercase:
  • abs(a - ord(b)) > k: Checks if the absolute difference between the ASCII values of the characters is greater than k, which means they cannot form an ideal sequence.
  • if b in d: If character b is within the difference k, and it's in dictionary d, then it's a candidate for creating or extending an ideal subsequence.
  • dp[i] = max(dp[i], dp[d[b]] + 1): Here, the dynamic programming comes into play. We update the dp[i] with the maximum of its current value or the length of the ideal subsequence ending with b plus one (to include the current character s[i]).
• d[s[i]] = i: We update or add the current character and its index to dictionary d to keep track of the last position it was seen.
• return max(dp): After filling the dp table, the length of the longest ideal subsequence will be the maximum value in the dp list.

By keeping track of the ideal subsequences ending with different characters and building upon each other, this algorithm efficiently finds the longest one possible.

Example Walkthrough

Let's consider a string s = "abcd" and k = 2, which signifies the maximum allowed absolute difference in the alphabetical order.

To illustrate the solution approach, we'll walk through the example step-by-step:

1. Initialization: We have n = 4 since the length of s is 4. We create a dp list of length n initialized with all 1s because the minimum subsequence length ending at each character is 1 (the character itself). We also have a dictionary, d, which will keep track of the last seen index for each character.

2. Starting Point: With s[0] = 'a', we initialize d with {'a': 0}. Since 'a' is the first character, dp[0] = 1.

3. Iteration with i = 1 for s[i] = 'b':

   • We check if 'a' can form an ideal subsequence with 'b'. Since abs(ord('a') - ord('b')) = 1 which is less than or equal to k, 'a' can form an ideal subsequence with 'b'.
   • Thus, we update dp[1] with the maximum of dp[1] and dp['a' index] + 1. Since dp[0] = 1, this means dp[1] becomes 2.
   • Update d to include 'b': 1.

4. Iteration with i = 2 for s[i] = 'c':

   • We check 'a' and 'b' to form an ideal subsequence with 'c'. Both are within k distance.
   • Since both 'a' and 'b' can precede 'c', we choose the one that provides the longest subsequence. dp[2] is updated to max(dp[2], dp['b' index] + 1), which is 3.
   • Update d to include 'c': 2.

5. Iteration with i = 3 for s[i] = 'd':

   • Repeat the above step for 'd', checking 'a', 'b', and 'c'. Again, all are within k distance.
   • We again choose the best predecessor, which is 'c' in this case. We update dp[3] to max(dp[3], dp['c' index] + 1), which is 4.
   • Update d to include 'd': 3.

6. Finish: We have processed all characters in s. The dp array is [1, 2, 3, 4], and thus the length of the longest ideal subsequence is max(dp) which is 4.

In this example, the longest ideal subsequence we can form from "abcd" with k = 2 is "abcd" itself, with the length of 4. However, for strings with repeating characters or larger alphabetic differences, we would see more variation in the dp updates based on which preceding characters provide the longer ideal subsequence according to the k condition.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n * 26 * k) where n is the length of the input string s and k is the maximum difference allowed for the ideal string. For each character in the string s, the code iterates over all 26 letters in the ascii_lowercase (regardless of k because it checks all possibilities within the range) to find characters within the allowed difference k. Therefore, we look at all possible 26 characters for each of the n positions in the worst case. Additionally, for each character b in ascii_lowercase, we look up in dictionary d which has an average-case lookup time of O(1). Hence, we multiply 26 by this constant lookup time, which doesn’t change the O-notation.

The space complexity of the code is O(n) because the dp array is of size n, where n is the size of the input string s. The dictionary d also stores up to n index values for all unique characters that have been seen. In this case, the number of unique keys in the dictionary is bounded by the size of the ascii_lowercase set, which is a constant (26), so it does not change the overall space complexity which is dominated by the dp array.

Learn more about how to find time and space complexity quickly using problem constraints.