Longest Distinct characters in string Geeks solution

Longest Distinct characters in string Geeks solution

  July 24, 2017    

---

Problem :

Given a string, find length of the longest substring with all distinct characters. 

 input
 abca

 output 
 3

 as "abc" is the longest substring with all distinct characters

Idea is to track the location of ith character and check if it comes in our substring.

Implementation:

We are storing the location of i th character of string in array "visited" and for every occurrence we are checking whether index of the character is there or not , if it is there then is it comes under our range of substring =>  if(prev==-1 || prev<i-curlen)

if not then increment current length else change current length by subtracting last occurrence of ith occurrence 

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static int check(String str)
     {
         int len=str.length();
         int max=1;
         int curlen=1;
         int prev;
         int visited[]=new int[10000];
         char[] st=str.toCharArray();
         Arrays.fill(visited,-1);
         visited[st[0]]=0;
         for(int i=1;i<len;i++)
         {
             prev=visited[st[i]];
             if(prev==-1 || prev<i-curlen)
             {
                 curlen++;
             }
             else
             {
                 max=Math.max(max,curlen);
                 curlen=i-prev;
             }
             visited[st[i]]=i;
         }
         return (max>curlen)?max:curlen;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   System.out.println(check(ab.next()));
}
}
}