diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /longest_ideal_subseq.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'longest_ideal_subseq.py')
-rw-r--r-- | longest_ideal_subseq.py | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/longest_ideal_subseq.py b/longest_ideal_subseq.py new file mode 100644 index 0000000..b5e05d8 --- /dev/null +++ b/longest_ideal_subseq.py @@ -0,0 +1,33 @@ +# 2370. Longest Ideal Subsequence + +""" +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 sting. 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. +""" + + +class Solution(object): + def longestIdealString(self, s, k): + """ + :type s: str + :type k: int + :rtype: int + """ + dp = [0] * 128 + for c in s: + i = ord(c) + dp[i] = max(dp[i - k : i + k + 1]) + 1 + return max(dp) + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestIdealString("acfbd", 2)) # expect: 4 + print(obj.longestIdealString("abcd", 3)) # expect: 4 |