# Longest Ideal Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-ideal-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-ideal-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, String
**Companies:** [MakeMyTrip](https://scaleengineer.com/companies/makemytrip)
---
## Problem
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.

# Approaches
## Brute-Force Dynamic Programming
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`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimized Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int longestIdealString(String s, int k) {
        // dp[i] stores the longest ideal subsequence ending with char 'a' + i
        int[] dp = new int[26]; 
        int result = 0;

        for (char c : s.toCharArray()) {
            int charIndex = c - 'a';
            int maxPrevLength = 0;
            
            // Find the max length of a subsequence ending with a character
            // within k distance of the current character.
            int start = Math.max(0, charIndex - k);
            int end = Math.min(25, charIndex + k);
            
            for (int j = start; j <= end; j++) {
                maxPrevLength = Math.max(maxPrevLength, dp[j]);
            }
            
            // Update the length for the current character
            dp[charIndex] = maxPrevLength + 1;
            
            // Update the overall result
            result = Math.max(result, dp[charIndex]);
        }
        
        return result;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestIdealString(string s, int k) {
    int n = s.size();
    int ans = 1;
    vector<int> dp(n, 1);
    unordered_map<char, int> d;
    d[s[0]] = 0;
    for (int i = 1; i < n; ++i) {
      char a = s[i];
      for (char b = 'a'; b <= 'z'; ++b) {
        if (abs(a - b) > k)
          continue;
        if (d.count(b))
          dp[i] = max(dp[i], dp[d[b]] + 1);
      }
      d[a] = i;
      ans = max(ans, dp[i]);
    }
    return ans;
  }
};

```

### Python

```python
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)

```