Go Program to Find the Longest Substring Without Repeating Characters

Introduction

Finding the longest substring without repeating characters is a common problem in string manipulation. The goal is to identify the longest sequence of unique characters within a given string. This guide will demonstrate how to write a Go program to solve this problem.

Problem Statement

Create a Go program that:

• Prompts the user to enter a string.
• Finds the longest substring within that string that does not contain any repeating characters.
• Displays the length of the longest substring and the substring itself.

Example:

• Input: "abcabcbb"
• Output: Longest substring without repeating characters: "abc" with length 3

Solution Steps

1. Import the fmt Package: Use import "fmt" for formatted I/O operations.
2. Write a Function to Find the Longest Substring Without Repeating Characters: Implement a function that uses a sliding window technique.
3. Write the Main Function: Define the main function, which is the entry point of every Go program.
4. Prompt the User to Enter a String: Use fmt.Scanln or fmt.Scanf to take input from the user.
5. Call the Function to Find the Longest Substring: Use the function to determine the longest substring without repeating characters.
6. Display the Result: Use fmt.Println to display the longest substring and its length.

Go Program

package main

import "fmt"

// Step 2: Implement a function to find the longest substring without repeating characters
func longestUniqueSubstring(s string) (int, string) {
    charIndexMap := make(map[rune]int)
    start := 0
    maxLength := 0
    longestSubstring := ""

    for i, char := range s {
        if prevIndex, found := charIndexMap[char]; found && prevIndex >= start {
            start = prevIndex + 1
        }
        charIndexMap[char] = i
        if i-start+1 > maxLength {
            maxLength = i-start+1
            longestSubstring = s[start : i+1]
        }
    }

    return maxLength, longestSubstring
}

/**
 * Go Program to Find the Longest Substring Without Repeating Characters
 * Author: https://www.javaguides.net/
 */
func main() {
    // Step 4: Prompt the user to enter a string
    var input string
    fmt.Print("Enter a string: ")
    fmt.Scanln(&input)

    // Step 5: Call the function to find the longest substring without repeating characters
    length, substring := longestUniqueSubstring(input)

    // Step 6: Display the result
    fmt.Printf("Longest substring without repeating characters: \"%s\" with length %d\n", substring, length)
}

Explanation

Step 2: Implement a Function to Find the Longest Substring Without Repeating Characters

• The longestUniqueSubstring function uses a sliding window technique:
  • It maintains a charIndexMap to store the last index at which each character was seen.
  • It iterates through the string, adjusting the start of the window when a repeating character is found.
  • The function keeps track of the maximum length of the substring without repeating characters and updates the longest substring whenever a new maximum is found.

Step 4: Prompt the User to Enter a String

• The program prompts the user to enter a string using fmt.Print and reads the input using fmt.Scanln.

Step 5: Call the Function to Find the Longest Substring

• The program calls longestUniqueSubstring to determine the longest substring without repeating characters.

Step 6: Display the Result

• The program prints the longest substring and its length using fmt.Printf.

Output Example

Example 1:

Enter a string: abcabcbb
Longest substring without repeating characters: "abc" with length 3

Example 2:

Enter a string: bbbbb
Longest substring without repeating characters: "b" with length 1

Example 3:

Enter a string: pwwkew
Longest substring without repeating characters: "wke" with length 3

Example 4:

Enter a string: abcdefghijklmnopqrstuvwxyz
Longest substring without repeating characters: "abcdefghijklmnopqrstuvwxyz" with length 26

Conclusion

This Go program demonstrates how to find the longest substring without repeating characters using a sliding window technique. It covers basic programming concepts such as string manipulation, maps, and efficient algorithms in Go. This example is useful for beginners learning Go programming and understanding how to solve common string-related problems efficiently.