[LeetCode] 2370. Longest Ideal Subsequence

https://leetcode.com/problems/longest-ideal-subsequence/description/

Leetcode - Longest Ideal Subsequence

문제 유형 : 다이나믹 프로그래밍, 문자열처리

문제 난이도 : Medium

 

문제

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

 

문자열 s와 정수 k를 받는다.

부분문자열 t는 s에서 특정 문자를 0개 이상 지우고, 순서를 바꾸지 않는 것으로 한다.

각 인접한 문자들끼리의 알파벳 차이가 k이하인 가장 긴 t를 구하시오.

알파벳의 순서는 사이클이 없습니다. a와 z의 차는 1이 아닌 25입니다.

 

풀이

처음에는 가장 긴 부분수열문제(LIS)와 유사하다고 생각했는데, 큰 발상의 전환이 필요했다.

dp[<인덱스>] = <t의길이>가 아니라,

dp[<마지막으로 삽입된 심벌>] = <t의길이>로 했어야 했다.

 

문자열을 순회하면서, 현재 읽은 글자가 몇 번째 알파벳인지 구하고, dp[해당 알파벳 번호] 에다가 이전 dp에 연결 가능한 부분들 중에서 가장 긴 부분과 결합한 것으로 간주하여 1을 더해서 누적시킨다.

즉, dp[max(해당 알파벳 번호-k, 0)] ~ dp[min(해당 알파벳 번호+k, 26)]중에서 가장 긴 값에 1을 더하면 된다. 

 

코드

C++

class Solution {
public:
    int longestIdealString(string s, int k) {
        vector<int> dp(27, 0);
        const int n = s.size();

        for(int i = n-1; i >= 0; i--) {
            char ch = s[i];
            int idx = ch - 'a';
            int len = -1;

            int left = max((idx - k), 0);
            int right = min((idx + k), 26);

            for(int j = left; j <= right; j++) {
                len = max(len, dp[j]);
            }

            dp[idx] = len+1;
        }

        return *max_element(dp.begin(), dp.end());
    }
};