We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Ideal Subsequence

Number: 2444

Difficulty: Medium

Paid? No

Companies: Amazon, MakeMyTrip

Problem Description

Given a string s and an integer k, find the length of the longest subsequence of s (called an "ideal" subsequence) such that the absolute difference between every two adjacent characters (in terms of their positions in the alphabet) is at most k.

Key Insights

  • We need to compute the longest subsequence that adheres to the constraint on adjacent character differences.
  • A dynamic programming approach works well since each character in s can be used to extend the ideal subsequence if its previous character is within k distance in the alphabet.
  • Maintain a DP array of size 26 where each entry represents the length of the longest ideal subsequence ending with the corresponding character.
  • For every new character, check all characters in the valid range (within k distance) and update the DP value.
  • Because there are only 26 letters and k is at most 25, iterating through a constant range yields an efficient solution.

Space and Time Complexity

Time Complexity: O(n * 26) ≈ O(n) (since k and 26 are constant factors) Space Complexity: O(26) which is O(1)

Solution

The solution uses dynamic programming with a one-dimensional array dp of size 26. Each index i in the array represents the maximum length of an ideal subsequence ending with the letter corresponding to i (i.e. 'a' + i). For each character in the string s:

  1. Convert the character to its index.
  2. Determine the lower and upper bounds for acceptable previous characters (taking into account k).
  3. Find the maximum dp value in that range.
  4. Update dp[current index] with maximum value + 1. Finally, return the maximum value from the dp array, which represents the length of the longest ideal subsequence.

Code Solutions

# Python solution
class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        # dp[i] represents longest ideal subsequence ending with the letter (chr(i + ord('a')))
        dp = [0] * 26
        
        # Iterate through each character in the input string s
        for char in s:
            index = ord(char) - ord('a')  # Find the index of the current character
            # Compute allowed range for previous characters based on k
            low = max(0, index - k)
            high = min(25, index + k)
            # Find the best previous subsequence length from allowed range
            bestPrev = max(dp[i] for i in range(low, high + 1))
            # Update dp value for current character
            dp[index] = max(dp[index], bestPrev + 1)
        
        # The result is the maximum value in dp array
        return max(dp)

# Example usage:
# sol = Solution()
# print(sol.longestIdealString("acfgbd", 2))  # Expected output: 4
← Back to All Questions