Given a string consisting of lower-case characters, find the longest subsequence such that the distance between adjacent characters in the subsequence are less than a given threshold.

Intuition

Same as the longest increasing subsequence, we can use dynamic programming to solve this problem.

Approach

However, it turns out that the above solution is of complexity $O(n^2)$, which leads to Time Exceed Limit, so we need to optimize it.

Now, consider the property of ideal sequence, we only care about those characters that is within the range (s[i - 1] - k, s[i - 1] + k). So, we can use a map record, whose key is all lowercase characters, to remember the result that is used to update dp[i], that is, for given index i:

notice that len(record)=26, so the complexity now reduces to $O(n)$.

Complexity

• $$O(n)$$
• $$O(n)$$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.size();
        vector<int> dp(n + 1);
        vector<int> record(26);
        for (int i = 0; i < n; ++i) {
            dp[i + 1] = 1;
            int index = s[i] - 'a';
            for (int j = 0; j < 26; ++j) {
                if (abs(index - j) <= k) {
                    dp[i + 1] = max(dp[i + 1], record[j] + 1);
                } 
            }
            record[index] = max(record[index], dp[i + 1]);
        }
        int result = 0;
        for (int i = 0; i < n + 1; ++i) {
            result = max(result, dp[i]);
        }
        return result;
    }
};