GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #2370 - Longest Ideal Subsequence - LeetCode JavaScript Solutions

#2370 - Longest Ideal Subsequence

Medium • View on LeetCode • View on GitHub

Problem Description

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.

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestIdealString = function(s, k) {
  const dp = new Array(26).fill(0);
  let result = 0;

  for (const char of s) {
    const idx = char.charCodeAt(0) - 97;
    let currentMax = 0;

    for (let i = Math.max(0, idx - k); i <= Math.min(25, idx + k); i++) {
      currentMax = Math.max(currentMax, dp[i]);
    }

    dp[idx] = currentMax + 1;
    result = Math.max(result, dp[idx]);
  }

  return result;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.