LeetCode 2370: Longest Ideal Subsequence

Explanation

To find the length of the longest ideal subsequence, we can use a dynamic programming approach. We can define a 2D array dp where dp[i][j] represents the length of the longest ideal subsequence ending at index i with a difference of j between the last two characters. We can then iterate over the string s and update the dp array based on the current character and the previous characters.

Algorithm:

1. Initialize a 2D array dp of size n x 26 where n is the length of the string s and 26 represents the number of lowercase letters.
2. Initialize all values in dp with 0.
3. Iterate over each character in the string s:
   • For each character c at index i, consider all possible characters prev that can precede c such that the difference between c and prev is less than or equal to k.
   • Update the dp[i][c - 'a'] with the maximum value of dp[prevIndex][prevChar - 'a'] + 1 for all valid prev characters.
4. Find the maximum value in the last row of dp to get the length of the longest ideal subsequence.

Time Complexity: The time complexity of this algorithm is O(n * k) where n is the length of the string s.

Space Complexity: The space complexity of this algorithm is O(n * 26) = O(n) where n is the length of the string s.

Solutions

class Solution {
    public int longestIdealSubsequence(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n][26];

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            for (char prev = 'a'; prev <= 'z'; prev++) {
                int prevIndex = i - 1;
                while (prevIndex >= 0 && Math.abs(c - prev) <= k) {
                    dp[i][c - 'a'] = Math.max(dp[i][c - 'a'], dp[prevIndex][prev - 'a'] + 1);
                    prevIndex--;
                }
            }
        }

        int maxLen = 0;
        for (int j = 0; j < 26; j++) {
            maxLen = Math.max(maxLen, dp[n - 1][j]);
        }

        return maxLen;
    }
}