Sponsored
Sponsored
This approach utilizes dynamic programming where we maintain an array "dp" of size 26 (number of alphabets) representing the longest ideal subsequence ending with each character from 'a' to 'z'. The value of dp[char] will be updated by considering the valid preceding characters which are within the range of 'k'. For each character in the string, we update our dp array by iterating over possible characters that are within distance 'k' in the alphabet. The maximum value in the dp array by the end of the iteration gives us the length of the longest ideal subsequence.
Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1), constant space for dp array.
1public class Solution {
2 public int longestIdealString(String s, int k) {
3 int[] dp = new int[26];
4 for (char ch : s.toCharArray()) {
5 int idx = ch - 'a';
6 int maxLen = 0;
7 for (int i = Math.max(0, idx - k); i <= Math.min(25, idx + k); i++) {
8 maxLen = Math.max(maxLen, dp[i]);
9 }
10 dp[idx] = maxLen + 1;
11 }
12 int result = 0;
13 for (int length : dp) {
14 result = Math.max(result, length);
15 }
16 return result;
17 }
18}The Java solution follows a similar logic. A dp array is initialized, and for each character, its index is calculated. It iterates over relevant indices within the range allowed by 'k', updating the maximum subsequence length and storing it back in the dp array. The result is determined by finding the maximum value in the dp array.
This approach leverages a HashMap to dynamically track the maximum subsequence length for characters encountered in the string, rather than maintaining a fixed size dp array. The HashMap keys represent characters and the values represent the maximum subsequence length possible for the corresponding character. For each character in the string, it checks and updates the longest subsequence length using nearby characters within distance 'k'.
Time Complexity: O(n * k), where n is the length of the string and k is the given integer. Space Complexity: O(26) = O(1).
1function longestIdealString(s, k) {
2This JavaScript code initializes an array dp of length 26 to keep track of the maximum length of the subsequence that ends with each character. It iterates over each character of the string, calculates its index in dp, and checks all indices that are within k-distance. The dp array is updated with the maximum value found plus one for the current character. The solution is returned as the maximum value in dp array.