Longest Ideal Subsequence - Practice Coding Problems

Longest Ideal Subsequence - 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: The alphabet order is not cyclic. For example, the absolute difference in the alphabet order of 'a' and 'z' is 25, not 1.

Input & Output

Example 1 — Basic Case

$ Input: s = "acfgik", k = 2

› Output: 4

💡 Note: The longest ideal string is "acik". Characters a→c (diff=2), c→i (diff=6>2 invalid), but a→c→g→i→k works where a→c (diff=2≤2), c→g invalid, but optimal path is a→c→e→g or similar giving length 4.

Example 2 — Large k

$ Input: s = "abcd", k = 3

› Output: 4

💡 Note: All adjacent characters have difference ≤3: |a-b|=1, |b-c|=1, |c-d|=1. The entire string "abcd" is ideal with length 4.

Example 3 — Small k

$ Input: s = "azbc", k = 1

› Output: 2

💡 Note: Can't include both 'a' and 'z' since |a-z|=25>1. Best subsequences are "ab", "bc", or "ac" (if valid). The longest has length 2.

Constraints

1 ≤ s.length ≤ 10⁵
0 ≤ k ≤ 25
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and compatibility distance k

Process

Find subsequence where adjacent chars differ by ≤ k

Output

Length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Use DP to track the longest subsequence ending at each character, extending only from compatible previous characters.

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is to use dynamic programming where dp[c] tracks the longest ideal subsequence ending with character c. For each character, we check all compatible previous characters (within distance k) and extend the best one. Best approach is 1D DP with Time: O(n×k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DP - Range Query	O(n log n)	O(1)	Use range maximum query to find best previous character efficiently
Dynamic Programming - 1D Array	O(n × k)	O(1)	Track longest ideal subsequence ending at each character
Brute Force - Generate All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and check which ones are ideal

Optimized DP - Range Query — Algorithm Steps

Maintain DP array where dp[c] = max length ending with character c
For each character, query range [char-k, char+k] for maximum DP value
Update current character's DP value = range_max + 1
Use segment tree or similar structure for efficient range queries

Visualization

Tap to expand

Step-by-Step Walkthrough

Current Char

Processing character with index i

Query Range

Find max in range [i-k, i+k]

Update DP

Set dp[i] = range_max + 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(char* s, int k) {
    // For small alphabet (26 chars), basic DP is often faster
    int dp[26] = {0};
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        int charIdx = s[i] - 'a';
        
        // Find range boundaries
        int left = max(0, charIdx - k);
        int right = min(25, charIdx + k);
        
        // Find maximum in range [left, right]
        int maxPrev = 0;
        for (int j = left; j <= right; j++) {
            maxPrev = max(maxPrev, dp[j]);
        }
        
        dp[charIdx] = maxPrev + 1;
    }
    
    int result = 0;
    for (int i = 0; i < 26; i++) {
        result = max(result, dp[i]);
    }
    return result;
}

int main() {
    char s[100001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each character update involves O(log n) range query and update operations

⚡ Linearithmic

Space Complexity

O(1)

Still using fixed size DP array for 26 characters

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DP - Range Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler