nalini.ambhore
BAN USERpublic void longestSubstring(string str1)
{
if(str1.Length < 1)
{
Console.WriteLine("string is empty");
return;
}
// to store the previous character index value
int[] characterIndex = new int[256];
int maxlength, startMaxIndex,currentIndex,lastMaxIndex ;
maxlength = startMaxIndex = currentIndex = lastMaxIndex = 0;
while(currentIndex < str1.Length)
{
// To set the uquine character condition
bool[] isRepeat = new bool[256];
int count, start, last, j;
last = count = 0;
start = j = currentIndex;
bool repeatresult = false;
// Condition to verify substring with unqiue characters
while (!repeatresult && j <= str1.Length -1)
{
if (j == str1.Length - 1)
currentIndex = j+1;
int charvalue = str1[j];
//condition Verifying the unqiue character
if (isRepeat[charvalue] == false )
{
// update index value where the character is seen in string
characterIndex[charvalue] = j;
isRepeat[charvalue] = true;
last = j; // tracking the last character position in current loop
count++; // tracking the count of unqiue characters
j++;
}
else
{
// setting the current index value to the previous occurance of the non-unqiue character for search of next unqiue sub string
currentIndex = characterIndex[charvalue] + 1;
characterIndex[charvalue] = j;
last = j - 1; // tracking the last unique character position in current loop
repeatresult = true;
}
}
// check for max lenght
if (count > maxlength)
{
// setting the max length sub string index value
maxlength = count;
startMaxIndex = start;
lastMaxIndex = last;
}
}
//Print the sub string
Console.WriteLine(" SubString Max length = {0} ", maxlength);
while (startMaxIndex <= lastMaxIndex)
{
Console.Write(str1[startMaxIndex]);
startMaxIndex++;
}
}
Solution using C# String Builder and time complexity = O(n)
- nalini.ambhore February 03, 2015