Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Solution:
When you have found a repeated character (let’s say at index j), it means that the current substring (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i is less than j.
Since you know that all substrings that start before or at index i would be less than your current maximum, you can safely start to look for the next substring with head which starts exactly at index i+1.
Therefore, you would need two indices to record the head and the tail of the current substring. Since i and j both traverse at most n steps, the worst case would be 2n steps, which the run time complexity must be O(n).
int lengthOfLongestSubstring(string s) { int n = s.length(); int i = 0, j = 0; int maxLen = 0; bool hash[256] = { 0 }; while (j < n) { if (hash[s[j]]) { maxLen = max(maxLen, j-i); while (s[i] != s[j]) { hash[s[i]] = 0; i++; } i++; j++; } else { hash[s[j]] = 1; j++; } } maxLen = max(maxLen, n-i); return maxLen; }
Time Complexity : O(N)
Admin you guys are already doing a great job.It would be much more useful if you can provide a short description of the logic also.
it will fail for “abcdeafghij”->longest substring would be bcdeafghij
Below is the solution
public static int LongestNonRepeatedChars(string str)
{
if (string.IsNullOrEmpty(str))
return 0;
if (str.Length == 1)
return 1;
Dictionary dictionaryStr = new Dictionary();
int maximum = 1;
int potentialMax = 1;
dictionaryStr.Add(str[0], str[0]);
for (int i = 1; i maximum)
{
maximum = potentialMax;
potentialMax = 1;
}
dictionaryStr.Clear();
}
dictionaryStr.Add(str[i], str[i]);
}
if (potentialMax > maximum)
maximum = potentialMax;
return maximum;
}
Here is the solution:
public void longestSubString(String str){
int count=0;
int maxlen=0;
int arr[] = new int[256];
for(int i=0;i<256;i++){
arr[i]=0;
}
int i=0;
int j=0;
while(imaxlen){
maxlen=count;
}
count–;
}
else{
arr[str.charAt(i)]=1;
count++;
i++;
}
}
if(count>maxlen){
maxlen=count;
}
System.out.println(“Longest Substrin:”+maxlen);
}
I made in this way (without array of 256 )
int longest_qnique_substr( char* string )
{
int limit = INT_MAX;
int min_limit = limit;
char *str = string;
int offset = 0;
while( *str && (str – string ) limit) ? limit :min_limit;
str++;
offset++;
}
return min_limit;
}
#include
#include
#include
using namespace std;
stack s;
int main()
{
string a;
int b[100]={0};
getline(cin,a);
int m=0;
for(int i=0; i<a.length(); i++)
{
if(i==0)
{
s.push(a[i]);
b[m]++;
}
else
{
if(a[i]==s.top())
{
s.push(a[i]);
m++;
}
else
{
b[m]++;
s.push(a[i]);
}
}
}
int c;
c=s.size();
for(int i=0; i<c; i++)
cout<<b[i]<<"\n";
}