Java: Find length of the longest substring of a given string without repeating characters

Last update on December 21 2024 10:02:40 (UTC/GMT +8 hours)

Write a Java program to find the length of the longest substring of a given string without repeating characters.

Note:
1) Given string consists of English letters, digits, symbols and spaces.
2) 0 <= Given string length <= 5 * 104

Difficulty: Medium.
Company: Amazon, Google, Bloomberg, Microsoft, Adobe, Apple, Oracle, Facebook and more.

Input String : pickoutthelongestsubstring
The longest substring : [u, b, s, t, r, i, n, g]
The longest Substring Length : 8

Input String : ppppppppppppp
The longest substring : [p]
The longest Substring Length : 1

Input String : Microsoft
The longest substring : [M, i, c, r, o, s]
The longest Substring Length : 6

Sample Solution:

Java Code:

import java.util.LinkedHashMap;
public class Main {
    // Method to find the longest substring with non-repeating characters
    static void longestSubstring(String inputString) {
        // Convert the inputString to a character array
        char[] arr1 = inputString.toCharArray();
        // Initialize variables to store the longest substring and its length
        String longestSubstring = "";
        int maxLength = 0;
        // Create a LinkedHashMap to store characters and their positions
        LinkedHashMap<Character, Integer> charPosMap = new LinkedHashMap<>();
        // Loop through the character array
        for (int i = 0; i < arr1.length; i++) {
            char ch = arr1[i];
            // Check if the character is not already present in the charPosMap
            if (!charPosMap.containsKey(ch)) {
                // If not present, add the character and its position to the map
                charPosMap.put(ch, i);
            } else {
                // If the character is present, update the start position of the substring
                // to the position after the repeated character
                i = charPosMap.get(ch);
                // Clear the map to start anew for the next non-repeating substring
                charPosMap.clear();
            }
            // Check if the current substring length is greater than the stored length
            if (charPosMap.size() > maxLength) {
                // If yes, update the longest substring and its length
                maxLength = charPosMap.size();
                // Extract the substring from the inputString using start and end indices
                longestSubstring = inputString.substring(i - maxLength + 1, i + 1);
            }
        }
        // Print the original inputString, the longest substring found, and its length
        System.out.println("Input String: " + inputString);
        System.out.println("The longest substring: " + longestSubstring);
        System.out.println("The longest Substring Length: " + maxLength);
    }
    // Main method to execute the program
    public static void main(String[] args) {
        // Call the longestSubstring method with different input strings
        longestSubstring("pickoutthelongestsubstring");
        longestSubstring("ppppppppppppp");
        longestSubstring("Microsoft");
    }
}

Sample Output:

Input String: pickoutthelongestsubstring
The longest substring: ubstring
The longest Substring Length: 8
Input String: ppppppppppppp
The longest substring: p
The longest Substring Length: 1
Input String: Microsoft
The longest substring: Micros
The longest Substring Length: 6

Flowchart:

Java Code Editor:

Improve this sample solution and post your code through Disqus

Previous: Write a Java program to check whether two strings are interliving of a given string. Assuming that the unique characters in both strings.
Next: Write a Java program to print after removing duplicates from a given string.