Longest Substring With at Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters. Example 1 Input: s = "eceba", k = 2 Output: 3 Explanation: T is "ece" which its length is 3. Example 2 Input: s = "aa", k = 1 Output: 2 Explanation: T is "aa" which its length is 2. Solution class Solution { public int lengthOfLongestSubstringKDistinct(String s, int k) { Map<Character, Integer> countMap = new HashMap<>(); int left = 0; int max = 0; for(int i = 0; i < s.

by lek tin in "algorithm" access_time 2-min read

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Note You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

by lek tin in "algorithm" access_time 3-min read

Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. Example 1 Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".

by lek tin in "algorithm" access_time 2-min read