Question

How to find the longest substring without repeating characters in VB.NET

Answer 1

Imports System

Module 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)
    '
    Function LongestUniqueSubstringASCII(input As String) As String
        Dim seen(255) As Boolean

        Dim left As Integer = 0
        Dim right As Integer = 0
        Dim bestLeft As Integer = 0
        Dim bestRight As Integer = 0

        While right < input.Length
            Dim c As Integer = Convert.ToInt32(input(right))

            If seen(c) Then
                ' Shrink window until we remove the duplicate
                While Convert.ToInt32(input(left)) <> c
                    seen(Convert.ToInt32(input(left))) = False
                    left += 1
                End While
                left += 1 ' skip the duplicate itself
            Else
                seen(c) = True

                If right - left > bestRight - bestLeft Then
                    bestLeft = left
                    bestRight = right
                End If
            End If

            right += 1
        End While

        Return input.Substring(bestLeft, bestRight - bestLeft + 1)
    End Function

    Sub Main()
        Dim str As String = "xwwwqfwwxqwyq"
        Dim result As String = LongestUniqueSubstringASCII(str)

        Console.WriteLine("Input: " & str)
        Console.WriteLine("Longest substring without repeating characters: " & result)
    End Sub

End Module


'
' run:
'
' Input: xwwwqfwwxqwyq
' Longest substring without repeating characters: xqwy
'

 

70+ SQL courses for beginners and professionals

Answer 2

Imports System

Module 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)
    '
    Function LongestUniqueSubstring(input As String) As String
        Dim lastSeen(255) As Integer
        For i = 0 To 255
            lastSeen(i) = -1
        Next

        Dim left As Integer = 0
        Dim bestStart As Integer = 0
        Dim bestLength As Integer = 0

        For right As Integer = 0 To input.Length - 1
            Dim c As Integer = Convert.ToInt32(input(right))

            ' If character was seen inside the current window, move left
            If lastSeen(c) >= left Then
                left = lastSeen(c) + 1
            End If

            ' Update last-seen index
            lastSeen(c) = right

            ' Check if this window is the best so far
            Dim windowLength As Integer = right - left + 1
            If windowLength > bestLength Then
                bestLength = windowLength
                bestStart = left
            End If
        Next

        Return input.Substring(bestStart, bestLength)
    End Function

    Sub Main()
        Dim str As String = "xwwwqfwwxqwyq"
        Dim result As String = LongestUniqueSubstring(str)

        Console.WriteLine("Input: " & str)
        Console.WriteLine("Longest substring without repeating characters: " & result)
    End Sub

End Module


'
' run:
'
' Input: xwwwqfwwxqwyq
' Longest substring without repeating characters: xqwy
'

 

70+ SQL courses for beginners and professionals