1. Introduction

Finding the longest non-repeating substring in a given string is a common problem in string manipulation and algorithm design. A substring is a contiguous sequence of characters within a string, and a non-repeating substring does not have any duplicate characters. In this tutorial, we will write a Java program to find the longest non-repeating substring in a given string.

2. Program Steps

1. Define a main method to serve as the entry point of the program.

2. Declare and initialize a String from which we want to find the longest non-repeating substring.

3. Initialize variables to keep track of the start index, maximum length, and the current length of the non-repeating substring.

4. Use a HashMap to store the last index of each character encountered.

5. Loop through each character of the string.

6. If the character is not present in the map or its index is before the current start index, update the current length and maximum length.

7. Update the index of the current character in the map.

8. After the loop, determine the longest non-repeating substring using the start index and maximum length.

9. Print the longest non-repeating substring.

3. Code Program

import java.util.HashMap;

public class LongestNonRepeatingSubstring {

    public static void main(String[] args) {

        // Step 2: Declare and initialize a String
        String str = "javaconceptoftheday";

        // Step 3: Initialize variables to keep track of the substring
        int start = 0, maxLength = 0, currentLength = 0;

        // Step 4: Use a HashMap to store the last index of each character encountered
        HashMap<Character, Integer> indexMap = new HashMap<>();

        // Step 5: Loop through each character of the string
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // Step 6: If character is not present in map or is before current start, update lengths
            if (!indexMap.containsKey(c) || indexMap.get(c) < start) {
                currentLength++;
                maxLength = Math.max(maxLength, currentLength);
            } else {
                start = indexMap.get(c) + 1;
                currentLength = i - start + 1;
            }

            // Step 7: Update the index of the current character in the map
            indexMap.put(c, i);
        }

        // Step 8: Determine the longest non-repeating substring
        int startIndex = str.length() - (maxLength - start);
        String longestSubstring = str.substring(startIndex, startIndex + maxLength);

        // Step 9: Print the longest non-repeating substring
        System.out.println("Longest Non-Repeating Substring: " + longestSubstring);
    }
}

Output:

Longest Non-Repeating Substring: conceptoftheday

4. Step By Step Explanation

– Step 1: The main method is defined, serving as the starting point of the program.

– Step 2: A String named str is declared and initialized with the value "javaconceptoftheday".

– Step 3: Variables start, maxLength, and currentLength are initialized to keep track of the non-repeating substring.

– Step 4: A HashMap named indexMap is used to store the last index of each character encountered.

– Step 5: A for loop is used to iterate through each character of the string.

– Step 6: Inside the loop, we check if the character is not in the map or its index is before the current start index, and update the lengths accordingly.

– Step 7: The index of the current character in the string is updated in the indexMap.

– Step 8: After the loop, we determine the longest non-repeating substring using the start index and maximum length.

– Step 9: The longest non-repeating substring is printed to the console.

This program efficiently finds the longest non-repeating substring in a given string using a sliding window approach and a HashMap to keep track of the indices of the characters.