Advertisement
ivandrofly

longest non-repeating substring

Feb 24th, 2021
1,125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.98 KB | None | 0 0
  1. namespace LongestSubstring
  2. {
  3.     using System;
  4.  
  5.     internal class Program
  6.     {
  7.         // This function returns true if all characters in
  8.         // str[i..j] are distinct, otherwise returns false
  9.         public static bool AreDistinct(string str, int i, int j)
  10.         {
  11.  
  12.             // Note : Default values in visited are false
  13.             bool[] visited = new bool[26];
  14.  
  15.             for (int k = i; k <= j; k++)
  16.             {
  17.                 if (visited[str[k] - 'a'] == true)
  18.                 {
  19.                     return false;
  20.                 }
  21.  
  22.                 visited[str[k] - 'a'] = true;
  23.             }
  24.             return true;
  25.         }
  26.  
  27.         // Returns length of the longest substring
  28.         // with all distinct characters.
  29.         public static int LongestUniqueSubsttr(string str)
  30.         {
  31.             int n = str.Length;
  32.  
  33.             // Result
  34.             int res = 0;
  35.  
  36.             for (int i = 0; i < n; i++)
  37.             {
  38.                 for (int j = i; j < n; j++)
  39.                 {
  40.                     if (AreDistinct(str, i, j))
  41.                     {
  42.                         res = Math.Max(res, j - i + 1);
  43.                     }
  44.                     else
  45.                     {
  46.                         // note: newly added to avoid going n time when there is a duplication in some n[i]
  47.                         i = j - 1; // it will be adjusted by the for loop
  48.                         break;
  49.                     }
  50.                 }
  51.             }
  52.  
  53.             return res;
  54.         }
  55.  
  56.         // Driver code
  57.         public static void Main()
  58.         {
  59.             string str = "geeksforgeeks";
  60.             Console.WriteLine("The input string is " + str);
  61.  
  62.             int len = LongestUniqueSubsttr(str);
  63.  
  64.             Console.WriteLine("The length of the longest " +
  65.                               "non-repeating character " +
  66.                               "substring is " + len);
  67.  
  68.             Console.ReadLine();
  69.         }
  70.     }
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement