Find Longest Substring Without Repeating Characters Java Program

Program: 

Find longest substring without repeating characters?

Description:
Given a string, find the longest substrings without repeating characters. Iterate through the given string, find the longest maximum substrings.

Code:

package com.java2novice.algos;

import java.util.HashSet;
import java.util.Set;

public class MyLongestSubstr {

    private Set<String> subStrList = new HashSet<String>();
    private int finalSubStrSize = 0;
    
    public Set<String> getLongestSubstr(String input){
        //reset instance variables
        subStrList.clear();
        finalSubStrSize = 0;
        // have a boolean flag on each character ascii value
        boolean[] flag = new boolean[256];
        int j = 0;
        char[] inputCharArr = input.toCharArray();
        for (int i = 0; i < inputCharArr.length; i++) {
            char c = inputCharArr[i];
            if (flag[c]) {
                extractSubString(inputCharArr,j,i);
                for (int k = j; k < i; k++) {
                    if (inputCharArr[k] == c) {
                        j = k + 1;
                        break;
                    }
                    flag[inputCharArr[k]] = false;
                }  
            } else {
                flag[c] = true;
            }
        }
        extractSubString(inputCharArr,j,inputCharArr.length);
        return subStrList;
    }
    
    private String extractSubString(char[] inputArr, int start, int end){
        
        StringBuilder sb = new StringBuilder();
        for(int i=start;i<end;i++){
            sb.append(inputArr[i]);
        }
        String subStr = sb.toString();
        if(subStr.length() > finalSubStrSize){
            finalSubStrSize = subStr.length();
            subStrList.clear();
            subStrList.add(subStr);
        } else if(subStr.length() == finalSubStrSize){
            subStrList.add(subStr);
        }
        
        return sb.toString();
    }

    public static void main(String a[]){
        MyLongestSubstr mls = new MyLongestSubstr();
        System.out.println(mls.getLongestSubstr("java2novice"));
        System.out.println(mls.getLongestSubstr("java_language_is_sweet"));
        System.out.println(mls.getLongestSubstr("java_java_java_java"));
        System.out.println(mls.getLongestSubstr("abcabcbb"));
    }
}

Output:

[a2novice]
[uage_is]
[_jav, va_j]
[cab, abc, bca]

To find the longest substring without repeating characters in Java, you can use a sliding window approach with a HashMap to keep track of the characters and their positions. Here's a Java program that demonstrates this approach:

import java.util.HashMap;

import java.util.Map;

public class LongestSubstringWithoutRepeating {

    public static void main(String[] args) {

        String input = "abcabcbb";

        System.out.println("The longest substring without repeating characters in '" + input + "' is: " + 

                            findLongestSubstring(input));

    }

    public static String findLongestSubstring(String s) {

        int n = s.length();

        int maxLength = 0;

        int start = 0;

        int startOfLongest = 0;

        

        Map<Character, Integer> map = new HashMap<>();

        for (int end = 0; end < n; end++) {

            char currentChar = s.charAt(end);

            if (map.containsKey(currentChar)) {

                start = Math.max(start, map.get(currentChar) + 1);

            }

            map.put(currentChar, end);

            if (end - start + 1 > maxLength) {

                maxLength = end - start + 1;

                startOfLongest = start;

            }

        }

        return s.substring(startOfLongest, startOfLongest + maxLength);

    }

}

Explanation:

1. Variables:

   • n: Length of the input string.
   • maxLength: The length of the longest substring found.
   • start: The start index of the current window (substring being considered).
   • startOfLongest: The start index of the longest substring found.

2. HashMap: Used to store the last occurrence of each character.

3. Sliding Window:

   • Iterate through the string using end as the end index of the window.
   • For each character at end, check if it is already in the map (which means it has occurred before within the current window).
   • If it is, update the start position to be one more than the last occurrence of the character to avoid repeating characters within the window.
   • Update the position of the current character in the map.
   • Update maxLength and startOfLongest if the current window is longer than the previously found longest substring.

4. Result: Return the longest substring using the substring method with startOfLongest and maxLength.

This program will output the longest substring without repeating characters for a given input string. For example, given the input "abcabcbb", the output will be "abc".