Skip to content

Instantly share code, notes, and snippets.

@marta-krzyk-dev
Created October 23, 2019 21:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save marta-krzyk-dev/28b7c50a60033e6f4a67faa9804d35d1 to your computer and use it in GitHub Desktop.
Save marta-krzyk-dev/28b7c50a60033e6f4a67faa9804d35d1 to your computer and use it in GitHub Desktop.
Find longest substring with unique 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