Advertisement
ivandrofly

The longest substring without repeating letters

Mar 5th, 2015
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.61 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace ConsoleApplication1
  8. {
  9.     class Program
  10.     {
  11.         static void Main(string[] args)
  12.         {
  13.             var input = "abcdeabcdebb";
  14.             var output = lengthOfLongestSubstring(input);
  15.             Console.WriteLine(output);
  16.             input = "bbbbaaa";
  17.             output = lengthOfLongestSubstring(input);
  18.             Console.WriteLine(output);
  19.             Console.ReadLine();
  20.             // The longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.
  21.             // for "bbbbb" the longest substring "b" with the length of 1.
  22.         }
  23.  
  24.  
  25.         static int lengthOfLongestSubstring(string s)
  26.         {
  27.             int i = 0, j = 0;
  28.             int maxLen = 0;
  29.  
  30.             // Set all characters as not-existing
  31.             var exist = new bool[256];
  32.  
  33.             while (j < s.Length) // Get the length of string
  34.             {
  35.                 // Check if the character exists
  36.                 if (exist[s[j]])
  37.                 {
  38.                     maxLen = Math.Max(maxLen, j - i);
  39.                     while (s[i] != s[j])
  40.                     {
  41.                         exist[s[i]] = false;
  42.                         i++;
  43.                     }
  44.  
  45.                     i++;
  46.                     j++;
  47.                 }
  48.                 else
  49.                 {
  50.                     exist[s[j]] = true;
  51.                     j++;
  52.                 }
  53.             }
  54.             return maxLen = Math.Max(maxLen, s.Length - i);
  55.         }
  56.     }
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement