thảo luận Leetcode mỗi ngày

class Solution:
    @cache
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        else:
            return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)

class Solution {
    public int tribonacci(int n) {
        if (n < 2) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0]*26
        ans = 0
        for char in s:
            index = ord(char) - ord('a')
            longestIdealSubsequence = 0
            for i in range(max(index - k, 0), min(index + k + 1, 26)):
                longestIdealSubsequence = max(longestIdealSubsequence, dp[i])
            
            dp[index] = longestIdealSubsequence + 1
            ans = max(ans, dp[index])
        return ans

int longestIdealString(string s, int k) {
    int dp[26] = {};
    int res = 0;
    for (auto& i : s) {
        i = i - 'a';
        for (int j = max(i - k, 0); j <= min(25, i + k); ++j)
            dp[i] = max(dp[i], dp[j]);
        res = max(res, ++dp[i]);
    }
    return res;
}

function longestIdealString(s: string, k: number): number {
    const dp: number[] = Array(128).fill(0);

    for (const c of s) {
        const i: number = c.charCodeAt(0);
        const start: number = Math.max(0, i - k);
        const end: number = Math.min(127, i + k + 1);
        dp[i] = Math.max(...dp.slice(start, end)) + 1;
    }

    return Math.max(...dp);
}

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        length = [0] * 26
        
        for char in s:
            order = ord(char) - ord('a')
            length[order] = max(length[max(0, order - k) : min(25, order + k)+1]) + 1
            
        return max(length)

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        longest_chr = [0]*26
        for c in s:
            start = max(0, ord(c)-97-k)
            end = min(26, ord(c)-97+k)
            longest_chr[ord(c)-97] = max(longest_chr[start:end+1])+1
        return max(longest_chr)

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        map = defaultdict(int)
        n = len(s)
        dp = [0] * n
        for i, c in enumerate(s):
            map[c] = max(0, map[c])
            start, end = max(97, ord(c) - k), min(122, ord(c) + k) + 1
            v = 0
            for j in range(start, end):
                # c1: char from int
                if c1 in map:
                    v = max(v, map[c1] + 1)
            dp[i] = v
            map[c] = v

        return max(dp)

class Solution {
    public int longestIdealString(String s, int k) {
        char[] c = s.toCharArray();
        int[] dp = new int[c.length];
        int[] letter = new int [26];
        Arrays.fill(letter, -1);
        letter[c[0]-'a']=0;
        Arrays.fill(dp,1);
        for(int i =1 ;i<c.length;i++){
            for(int j=0;j<=k;j++){
                int ci = c[i]-'a';
                if(ci-j>=0 && letter[ci-j]!=-1){
                    dp[i]=Math.max(dp[i],dp[letter[ci-j]]+1);
                }
                if(ci+j<26 && letter[ci+j]!=-1){
                    dp[i]=Math.max(dp[i],dp[letter[ci+j]]+1);
                }
            }
            letter[c[i]-'a']=i;
        }
        int ans =0;
        for(int i:dp){
            ans=Math.max(ans,i);
        }
        return ans;
    }
}

class Solution {
public:
    int longestIdealString(string s, int k) {
        int dp[26] = {0};
        for (char &c : s) {
            int i = c-'a', t = 0;
            for (int j = max(i-k,0); j <= min(i+k,25); j++) t = max(t,dp[j]);
            dp[i] = t+1;
        }
        return *max_element(dp,dp+26);
    }
};

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        maxHash = [0 for i in range(26)]
        for char in s:
            charHash = ord(char) - 97
            maxCur = 0
            minRange = max(0, charHash - k)
            maxRange = min(25, charHash + k)
            maxHash[charHash] = max(maxHash[minRange:maxRange+1]) + 1
        return max(maxHash)

var longestIdealString = function(s, k) {
    const arr = Array.from({ length: 26 }, () => 0);
    const rmq = (l, h) => {
        let i = l;
        for (let j = l + 1; j < h; j++) {
            if (arr[j] > arr[i]) {
                i = j;
            }
        }
        return i;
    }
    const sub = (u, v) => {
        return u.charCodeAt(0) - v.charCodeAt(0);
    }
    for (const ch of s) {
        const l = Math.max(0, sub(ch, 'a') - k);
        const h = Math.min(26, sub(ch, 'a') + k + 1);
        const i = rmq(l, h);
        arr[sub(ch, 'a')] = arr[i] + 1;
    }
    return _.max(arr);
};

class Solution(object):
    def longestIdealString(self, s, k):
        dp = [0] * 26
        for c in s:
            curr = ord(c) - 97
            dp[curr] = 1 + max(dp[max(curr - k, 0) : min(curr + k + 1 , 26)])
        return max(dp)