Find Longest Substring Without Repeating Characters | Java and Python

Print Length of Longest Substring Without Repeating Characters from given String using Sliding Window Algorithm

Problem Description :

Given a string s, find the length of the longest substring without repeating characters. string consists of English letters, digits, symbols and spaces.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = " " (Space) Output: 1 Explanation: The answer is " ", with the length of 1.

Example 4:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3.

Here we will use Sliding Window technique for solving this problem. We will also solve this prolem using using nested loop (Brute force technique).

What is Sliding Window?

Sliding Window is a computational technique which aims to reduce the use of nested loop and replace it with a single loop, thereby reducing the time complexity.

Learn more about Sliding Window technique :

• Sliding Window Technique 

Solution 1 : Print  Longest SubString Without Repeating Characters in Java using Sliding Window

import java.util.HashMap;
import java.util.Scanner;

public class LongestSubstringWithoutRepeatingCharacters {

    public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
       
        System.out.println("enter string");
        String s = sc.nextLine();
       
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max, i-j+1);
        }
       
        System.out.println(max);
    }

}

Solution Explanation :

• We will HashMap, which stores the characters in string as keys and their positions as values.
  
• Two pointers i and j, i tracks entire string from 0 to length and j tracks last repeated character. 
• Map values keep changing as i pointer increment.
• If the character is already in the Map, then move the j pointer to the right of the same character last found.

Solution 2 : Find Longest SubString Without Repeating Characters in Java using Nested loop

import java.util.Scanner;

public class LongestSubstringWithoutRepeatingCharacters {

    public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
       
        System.out.println("enter string");
        String s = sc.nextLine();

        int max = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            int j = i;
            StringBuilder builder = new StringBuilder();
            while (j < array.length) {
                int contains = builder.indexOf(Character.toString(j));
                if (contains == -1) {
                    builder.append(s);
                    if (max < builder.length()) {
                        max = builder.length();
                    }
                } else {
                    break;
                }
                j++;
            }
        }
        System.out.println(max);
    }
}

Solution Explanation :

• Using for loop, traverse through entire given string.
• In while loop, maintain substring using StringBuilder that are contains only unique elements.
• If repeated character found, get length of StringBuffer.
• Print max longest substring.

Solution 3 : Print  Longest Substring Without Repeating Characters in Python

class LongestSubstringWithoutRepeatingCharacters:

    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        repatedChar = {}
        
        for i in range(len(s)):
            if s[i] in repatedChar and start <= repatedChar[s[i]]:
                start = repatedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            repatedChar[s[i]] = i

        print (maxLength);

 

 RECOMMENDED ARTICLES :

1. Print Array Index of two sum equals to given Target from Sorted Array
2. Rotate Array with given n number without extra space 
3. Print Pascal's Triangle by given index 
4. Merge Two Sorted Array with Explanation