Problem Description

You are given a string s containing only lowercase letters and an integer k. Your task is to find the length of the longest "ideal string" that can be formed.

An ideal string t must satisfy two conditions:

1. t must be a subsequence of s (you can obtain t by deleting some or no characters from s without changing the order of remaining characters)
2. For every pair of adjacent letters in t, their absolute difference in alphabetical position must be at most k

The alphabetical position difference is calculated as the absolute difference between the positions of letters in the alphabet. For example:

• The difference between 'a' (position 1) and 'c' (position 3) is |1 - 3| = 2
• The difference between 'b' (position 2) and 'e' (position 5) is |2 - 5| = 3
• The difference between 'a' (position 1) and 'z' (position 26) is |1 - 26| = 25

Note that the alphabet is not cyclic - 'a' and 'z' are 25 positions apart, not 1.

Example: If s = "acfgbd" and k = 2:

• "acf" is NOT ideal because 'c' and 'f' have a difference of 3 (> 2)
• "ab" is ideal because 'a' and 'b' have a difference of 1 (≤ 2)
• "acd" is ideal because 'a' and 'c' have difference 2, and 'c' and 'd' have difference 1

The goal is to return the length of the longest possible ideal string.

Intuition

This problem asks for the longest subsequence with a constraint on adjacent elements, which immediately suggests dynamic programming. The key insight is that we need to track the longest ideal string ending at each position.

For each character in the string, we need to decide: should we start a new ideal string from this character, or extend an existing ideal string? To extend an existing ideal string, the current character must be within k distance from the last character of that string.

The challenge is efficiently finding which previous characters can connect to our current character. Since we're dealing with lowercase letters (only 26 possible values), we can check all possible previous characters that are within k distance. For the current character with ASCII value a, any character with ASCII value in the range [a-k, a+k] can be its predecessor in an ideal string.

However, when multiple positions have the same character, we only need to remember the most recent one, as it will have the maximum dp value among all occurrences of that character (since dp values are non-decreasing as we process the string left to right).

This leads to the approach:

1. Use dp[i] to store the length of the longest ideal string ending at position i
2. Maintain a dictionary d that maps each character to its most recent position in the string
3. For each position i, check all 26 lowercase letters to see which ones are within k distance and have appeared before
4. Update dp[i] based on the best predecessor found
5. Update the dictionary with the current character's position

The time complexity becomes O(26 * n) which is effectively O(n) since 26 is a constant, making this solution efficient even for large strings.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with a character-to-position mapping optimization. Here's how the implementation works:

Data Structures:

• dp[i]: Stores the length of the longest ideal string ending at position i
• d: Dictionary mapping each character to its most recent position in the string

Algorithm Steps:

1. Initialize the base case:

   dp = [1] * n  # Each character can start an ideal string of length 1
   d = {s[0]: 0}  # Store the first character's position

2. Process each character from position 1 to n-1:

   for i in range(1, n):
       a = ord(s[i])  # Get ASCII value of current character

3. Check all possible predecessor characters:

   for b in ascii_lowercase:
       if abs(a - ord(b)) > k:
           continue  # Skip if distance exceeds k

   For the current character s[i], we check all 26 lowercase letters. If a letter b has an absolute difference greater than k from s[i], it cannot be a valid predecessor.

4. Update dp[i] if valid predecessor exists:

   if b in d:
       dp[i] = max(dp[i], dp[d[b]] + 1)

   If character b has appeared before (exists in dictionary d), we can extend the ideal string ending at d[b] by adding the current character. We take the maximum to ensure we get the longest possible ideal string.

5. Update the dictionary with current character's position:

   d[s[i]] = i

   We always update to the most recent position because it will have the best (largest) dp value for that character.

6. Return the maximum value in dp array:

   return max(dp)

   The answer is the maximum length among all ideal strings ending at different positions.

Example Walkthrough:

For s = "acbd" and k = 2:

• Position 0 ('a'): dp[0] = 1, d = {'a': 0}
• Position 1 ('c'): Check 'a', 'b', 'c', 'd', 'e' (within distance 2)
  • 'a' exists in d, dp[1] = dp[0] + 1 = 2
  • Update d = {'a': 0, 'c': 1}
• Position 2 ('b'): Check 'a', 'b', 'c', 'd' (within distance 2)
  • 'a' exists: dp[2] = max(1, dp[0] + 1) = 2
  • 'c' exists: dp[2] = max(2, dp[1] + 1) = 3
  • Update d = {'a': 0, 'c': 1, 'b': 2}
• Result: max(dp) = 3

Example Walkthrough

Let's walk through a small example with s = "acfbd" and k = 2.

We'll track our dp array and dictionary d at each step:

Initial Setup:

• dp = [1, 1, 1, 1, 1] (each character can start an ideal string of length 1)
• d = {'a': 0} (first character 'a' at position 0)

Position 1 - character 'c':

• Current character 'c' has ASCII value 99
• Check all 26 letters to find valid predecessors (within distance k=2):
  • 'a' (ASCII 97): |99-97| = 2 ≤ 2 ✓ and 'a' exists in d at position 0
  • 'b' (ASCII 98): |99-98| = 1 ≤ 2 ✓ but 'b' not in d yet
  • 'c' (ASCII 99): |99-99| = 0 ≤ 2 ✓ but 'c' not in d yet
  • 'd' (ASCII 100): |99-100| = 1 ≤ 2 ✓ but 'd' not in d yet
  • 'e' (ASCII 101): |99-101| = 2 ≤ 2 ✓ but 'e' not in d yet
  • All other letters: distance > 2, skip
• Update: dp[1] = max(1, dp[0] + 1) = 2 (extend from 'a')
• Update dictionary: d = {'a': 0, 'c': 1}

Position 2 - character 'f':

• Current character 'f' has ASCII value 102
• Valid predecessors (within distance 2):
  • 'd' (ASCII 100): |102-100| = 2 ≤ 2 ✓ but not in d
  • 'e' (ASCII 101): |102-101| = 1 ≤ 2 ✓ but not in d
  • 'f' (ASCII 102): |102-102| = 0 ≤ 2 ✓ but not in d
  • 'g' (ASCII 103): |102-103| = 1 ≤ 2 ✓ but not in d
  • 'h' (ASCII 104): |102-104| = 2 ≤ 2 ✓ but not in d
• No valid predecessors exist in d
• dp[2] = 1 (start new ideal string)
• Update dictionary: d = {'a': 0, 'c': 1, 'f': 2}

Position 3 - character 'b':

• Current character 'b' has ASCII value 98
• Valid predecessors (within distance 2):
  • 'a' (ASCII 97): |98-97| = 1 ≤ 2 ✓ and exists at position 0
  • 'b' (ASCII 98): |98-98| = 0 ≤ 2 ✓ but not in d yet
  • 'c' (ASCII 99): |98-99| = 1 ≤ 2 ✓ and exists at position 1
  • 'd' (ASCII 100): |98-100| = 2 ≤ 2 ✓ but not in d
• Update: dp[3] = max(1, dp[0]+1, dp[1]+1) = max(1, 2, 3) = 3
• Update dictionary: d = {'a': 0, 'c': 1, 'f': 2, 'b': 3}

Position 4 - character 'd':

• Current character 'd' has ASCII value 100
• Valid predecessors (within distance 2):
  • 'b' (ASCII 98): |100-98| = 2 ≤ 2 ✓ and exists at position 3
  • 'c' (ASCII 99): |100-99| = 1 ≤ 2 ✓ and exists at position 1
  • 'd' (ASCII 100): |100-100| = 0 ≤ 2 ✓ but not in d yet
  • 'e' (ASCII 101): |100-101| = 1 ≤ 2 ✓ but not in d
  • 'f' (ASCII 102): |100-102| = 2 ≤ 2 ✓ and exists at position 2
• Update: dp[4] = max(1, dp[3]+1, dp[1]+1, dp[2]+1) = max(1, 4, 3, 2) = 4
• Update dictionary: d = {'a': 0, 'c': 1, 'f': 2, 'b': 3, 'd': 4}

Final Result:

• dp = [1, 2, 1, 3, 4]
• max(dp) = 4

The longest ideal string has length 4, which corresponds to the subsequence "acbd" where:

• 'a' to 'c': difference = 2 ≤ 2 ✓
• 'c' to 'b': difference = 1 ≤ 2 ✓
• 'b' to 'd': difference = 2 ≤ 2 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 26) = O(n)

The algorithm iterates through the string once with the outer loop running from index 1 to n-1, which takes O(n) time. For each character at position i, the inner loop iterates through all 26 lowercase letters (assuming ascii_lowercase contains 'a' to 'z'). For each letter, it performs constant time operations: checking the absolute difference, dictionary lookup, and updating the dp array. Since the inner loop runs exactly 26 times regardless of input size, the overall time complexity is O(n × 26) which simplifies to O(n).

Space Complexity: O(n)

The algorithm uses:

• A dp array of size n to store the longest ideal string ending at each position: O(n)
• A dictionary d that stores at most 26 entries (one for each lowercase letter) with the most recent index of each character: O(26) = O(1)
• A few integer variables (n, ans, a, b): O(1)

The dominant space usage is the dp array, making the overall space complexity O(n).

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

Common Pitfalls

Pitfall 1: Not Updating Character Positions Correctly

Issue: A common mistake is trying to track all positions where each character appears, rather than just the most recent position. This leads to unnecessary complexity and potential errors.

Incorrect Approach:

# Trying to maintain all positions for each character
positions = defaultdict(list)
for i in range(n):
    positions[s[i]].append(i)
    # Then checking all positions - inefficient!

Why it's problematic:

• You don't need to check all previous occurrences of a character
• The most recent occurrence will always have the best (largest) dp value for that character
• This increases time complexity unnecessarily

Correct Solution:

# Only track the most recent position
last_index[s[i]] = i  # Always overwrite with current position

Pitfall 2: Incorrect Distance Calculation

Issue: Confusing character distance with index distance, or incorrectly calculating alphabetical distance.

Incorrect Approaches:

# Wrong: Using index distance instead of character distance
if abs(i - j) > k:  # This checks position distance, not character distance

# Wrong: Subtracting characters directly
if abs(s[i] - s[j]) > k:  # Python doesn't allow direct string subtraction

Correct Solution:

# Convert characters to ASCII values first
if abs(ord(s[i]) - ord(candidate_char)) > k:

Pitfall 3: Forgetting Base Case Initialization

Issue: Not initializing dp array properly or forgetting to handle the first character.

Incorrect Approach:

dp = [0] * n  # Wrong: each character can form a subsequence of length 1
# or forgetting to initialize the dictionary
d = {}  # Missing first character

Correct Solution:

dp = [1] * n  # Each character is at least a subsequence of length 1
last_index = {s[0]: 0}  # Initialize with first character's position

Pitfall 4: Inefficient Character Checking

Issue: Only checking characters that appear in the string, missing potential valid predecessors.

Incorrect Approach:

# Only checking characters that exist in string s
for j in range(i):
    if abs(ord(s[i]) - ord(s[j])) <= k:
        dp[i] = max(dp[i], dp[j] + 1)

Why it's problematic:

• This approach has O(n²) time complexity for each position
• It might miss optimal solutions when intermediate characters don't appear in the string

Correct Solution:

# Check all 26 possible characters
for candidate_char in ascii_lowercase:
    if abs(ord(s[i]) - ord(candidate_char)) > k:
        continue
    if candidate_char in last_index:
        dp[i] = max(dp[i], dp[last_index[candidate_char]] + 1)

This ensures O(26n) = O(n) complexity and considers all valid predecessor characters.