Question

How to find the longest substring without repeating characters in C#

Answer 1

using System;

class Program
{
    /*
     * Finds the longest substring without repeating characters.
     * This version keeps a presence table and shrinks the window
     * by clearing characters until the duplicate is removed.
     *
     * Time complexity: O(n)
     */
    static string LongestUniqueSubstringASCII(string input)
    {
        bool[] seen = new bool[256];

        int left = 0;
        int right = 0;
        int bestLeft = 0;
        int bestRight = 0;

        while (right < input.Length)
        {
            int c = input[right];

            if (seen[c]) {
                // Shrink window until we remove the duplicate
                while (input[left] != input[right])
                {
                    seen[input[left]] = false;
                    left++;
                }
                left++; // skip the duplicate itself
            }
            else {
                seen[c] = true;

                if (right - left > bestRight - bestLeft) {
                    bestLeft = left;
                    bestRight = right;
                }
            }

            right++;
        }

        return input.Substring(bestLeft, bestRight - bestLeft + 1);
    }

    static void Main()
    {
        string str = "xwwwqfwwxqwyq";
        string result = LongestUniqueSubstringASCII(str);

        Console.WriteLine("Input: " + str);
        Console.WriteLine("Longest substring without repeating characters: " + result);
    }
}



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals

Answer 2

using System;

class Program
{
    /*
     * Finds the longest substring without repeating characters.
     * Uses a sliding window and a table of last-seen indexes.
     *
     * - lastSeen[c] stores the most recent index of character c.
     * - left/right define the current window.
     * - When a duplicate appears inside the window, move left forward.
     *
     * Time complexity: O(n)
     */
    static string LongestUniqueSubstring(string input)
    {
        int[] lastSeen = new int[256];
        for (int i = 0; i < 256; i++)
            lastSeen[i] = -1;

        int left = 0;
        int bestStart = 0;
        int bestLength = 0;

        for (int right = 0; right < input.Length; right++)
        {
            int c = input[right];

            // If character was seen inside the current window, move left
            if (lastSeen[c] >= left)
                left = lastSeen[c] + 1;

            // Update last-seen index
            lastSeen[c] = right;

            // Check if this window is the best so far
            int windowLength = right - left + 1;
            if (windowLength > bestLength) {
                bestLength = windowLength;
                bestStart = left;
            }
        }

        return input.Substring(bestStart, bestLength);
    }

    static void Main()
    {
        string str = "xwwwqfwwxqwyq";
        string result = LongestUniqueSubstring(str);

        Console.WriteLine("Input: " + str);
        Console.WriteLine("Longest substring without repeating characters: " + result);
    }
}



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals