instagram

Find length of longest substring of given string.

In this algorithm we just need length of longest sub string of given string. We are going to solve this by O(n)

Example :
Input : zabac
Output : 3

Just take a queue and add character in it one by one. Just before adding any new char, check if it is already there then remove it. after adding new char in queue compare it with max count.

remove part is little tricky. Lets see below example.

String s = “zabac”

Initially till first three char there are no repeating so queue has “zab”, now when we reach to 2nd “a”
we will see “a” is already there in queue, So we will remove one by one each character, Since this is FIFO queue, we are going to remove “z” first then “a” and then after removing 1st “a” we will add 2nd “a”. After adding 2nd “a” our string will look like this “ba”,

Share