Java Program to Find the Longest SubString Without Any Repeated Characters

This is the Java Program to Find the Longest SubString Without Any Repeated Characters

Problem Description

Given a string, find and print the longest substring without any repeating characters, that is all the characters in the substring must be unique.


String x = “ABBCDFGHC”
Output = “BCDFGH”

Problem Solution

Create a stack and push the first character of the string on it. Now, iterate through the string, and check whether the current character of the string is present in the stack or not. If it is present, update the longest substring as necessary.

Program/Source Code

Here is the source code of the Java Program to Find the Longest SubString Without Any Repeated Characters. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  2. // Java Program to Find the Longest SubString Without Any Repeated Characters.
  4. import;
  5. import;
  6. import java.util.Stack;
  8. public class LongestNonRepeatedSubstring {
  9.     // Function to find the longest non-repeating substring
  10.     static String longestSubstring(String str){
  11.         Stack<Character> stack = new Stack<>();
  12.         int last = 1;
  13.         int prev = 0;
  14.         String ans = "";
  15.         int i;
  16.         int max = -1;
  17.         stack.push(str.charAt(0));
  18.         for(i=1; i<str.length(); i++){
  19.             if( != -1){
  20.                 if((i-prev) > max){
  21.                     ans = str.substring(prev, i);
  22.                     max = i-prev;
  23.                 }
  24.                 prev  = i;
  25.                 stack.clear();
  26.                 stack.push(str.charAt(i));
  27.             }
  28.             else{
  29.                 stack.push(str.charAt(i));
  30.             }
  31.         }
  32.         if((i-prev) > max){
  33.             ans = str.substring(prev, i);
  34.         }
  35.         return ans;
  36.     }
  37.     // Function to read input and display the output
  38.     public static void main(String[] args) {
  39.         BufferedReader br = new BufferedReader(new InputStreamReader(;
  40.         String str;
  41.         System.out.println("Enter the text string");
  42.         try{
  43.             str = br.readLine();
  44.         }catch (Exception e){
  45.             System.out.println("An error occurred");
  46.             return;
  47.         }
  48.         String ans = longestSubstring(str);
  49.         System.out.println("The longest substring without any repeated"
  50.                                              + " characters is " + ans);
  51.     }
  52. }
Program Explanation

1. In function longestSubstring(), a stack is created to hold the characters and the first character of the string is pushed onto it.
2. The variables prev and last are used to store the starting and ending indexes of the substring and max stores the length of the longest substring.
3. The loop for(i=1; i<str.length(); i++) iterates through the string.
4. The condition if( != -1) checks if the current character of the string is already present in the stack.
5. If it is, the condition if((i-prev) > max) checks if the length of the current substring from prev to i is greater than the previous substring.
6. If it is, the max and ans variables are updated accordingly and the stack is cleared.
7. In case of the condition is point 4 failing, the current character is pushed onto the stack.
8. The longest substring is returned.

Time Complexity: O(n) where n is the length of the string.

Runtime Test Cases
Case 1 (Simple Test Case): 
Enter the text string
The longest substring without any repeated characters is BCDFGH
Case 2 (Simple Test Case - another example):
Enter the text string
The longest substring without any repeated characters is ZQWERTYKLA

Sanfoundry Global Education & Learning Series – Java Programs.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.