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 ;
}
---------------------------------------------------------------------------------
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
Post a Comment