Created
October 23, 2019 21:23
-
-
Save marta-krzyk-dev/28b7c50a60033e6f4a67faa9804d35d1 to your computer and use it in GitHub Desktop.
Find longest substring with unique characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections; | |
namespace LongestSubstring | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
string input = "abrkaabcdefghijjxxx"; | |
Console.WriteLine($"Length of longest substring with unique characters: {lengthOfLongestSubstring(input)}"); | |
Console.ReadKey(); | |
} | |
//This algorithm is of linear complexity O(n) | |
static int lengthOfLongestSubstring(string input) | |
{ | |
if (input is null) | |
return 0; | |
if (input.Length < 2) | |
return input.Length; | |
int longest = 1, current = 1; | |
Hashtable hashtable = new Hashtable(); | |
hashtable.Add(input[0], null); | |
for(int i = 1; i < input.Length; ++i) | |
{ | |
if (hashtable.ContainsKey(input[i])) | |
{ | |
if (current > longest) | |
{ | |
longest = current; | |
Console.WriteLine("Longest substring found is: " + longest); | |
} | |
hashtable.Clear(); //Get ready for finding another substring | |
current = 0; //Flush the counter | |
} | |
else // Every character is unique so far, keep adding | |
{ | |
++current; | |
hashtable.Add(input[i], null); | |
} | |
} | |
return longest; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment