Longest Distinct characters in string

PROBLEM :

Given a string, find length of the longest substring with all distinct characters.  For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is String str.

Output:

Print length of smallest substring with maximum number of distinct characters.
Note: The output substring should have all distinct characters.

Constraints:

1 = T = 100
1 = size of str = 10000

Example:

Input
2
abababcdefababcdab
geeksforgeeks

Output:
6
7

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry)
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<string.h>
int Longest_Distinct_characters_string(string ) ;
int main()
 {
int t,ans ;
string str ;
cin>>t ;
while(t--)
{
   cin>>str ;
   ans=Longest_Distinct_characters_string(str) ;
 
   cout<<ans<<endl ;
}
return 0;
}

int Longest_Distinct_characters_string(string str)
{
    int l,i,j,count,max ;
    l=str.length() ;
    max=0 ;
   
    for(i=0;i<l;i++)
    {
        int hash[256]={0} ;
        count=0 ;
        for(j=i;j<l;j++)
        {
            if(hash[str[j]]==0)
            {
                hash[str[j]]++ ;
                count++ ;
            }
            else
                break ;
        }
        if(max<count)
            max=count ;
    }
    return max ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )