TheLeanProgrammer
Published in

TheLeanProgrammer

Longest Substring with K Distinct Characters

JS|Sliding Window Technique

The best thing I came across was the problem-solving patterns like Sliding Window. Following this pattern helped me nurture my ability to map a new problem to an already known problem.

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.
Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Let’s use here sliding window approach with two set pointers start_window and currentWindowlength serving as the window boundaries. This algorithmic technique is used when we need to handle the input data in a specific window size.

Algorithm:

  • Set two both pointers at the beginning of the string start_window = 0 and currentWindowlength = 0 and init max substring length max_len = 0.
  • While the dict object keys are less than K distinct characters, add the current character in the dict object
  • If dict object contains k+1 distinct characters, remove the leftmost character from dict and move the start_window to right. so that the sliding window contains again k distinct characters only.
  • update maxLength
  • Return 0 if the string is empty or k is equal to zero.
var lengthOfLongestSubstringKDistinct = function(s, k) {
let dict = {};
let currentWindowlength = 0;
let start_window = 0, maxLength = 1;
for (let i = 0; i < s.length; i++) {
let char = s[i];
dict[char] = i;
if (Object.keys(dict).length > k) {
start_window = Math.min.apply(null, Object.values(dict));
delete dict[s[start_window]];
start_window++;
}
currentWindowlength = i - start_window + 1;
maxLength = Math.max(currentWindowlength, maxLength);
}
return maxLength;
};
lengthOfLongestSubstringKDistinct("eceba", 2)

Complexity Analysis

  • Time complexity: O(N)
  • Space complexity: O(k) since additional space is used only for an ordered dictionary with at most k + 1 elements.

If you want to learn more on data structure, book a session with me on www.startlearncoding.com

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer

--

--

--

The biggest power in the world is to be able to give life to something, and guess what? Code gives you this ability! Here in this publication, we build stuff, we share knowledge in tech, and share our stories, feel free to join — https://theleanprogrammer.com/writer-request/

Recommended from Medium

How to Create Dictionaries in JavaScript

Hack The Box “Canvas” Challenge

Run Express (Node.js) as a service on Windows

Will Rome Replace Webpack?

Will Rome Replace Webpack?

How V8 optimizes functions in JavaScript?

Assigning a variable in JS. Var vs Let vs Const

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
iAmSonika | www.startlearncoding.com

iAmSonika | www.startlearncoding.com

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

More from Medium

How to Use the Counting Sort Algorithm in JavaScript

Creating a Singly Linked List in JavaScript.

[Data Structure & Algorithm]: Binary Search with Javascript

What is a Linked List? How to Implement Singly Linked List in JavaScript

A visual represenataion of a linked list