Home » Core Java » Longest Substring Without Repeating Characters

About Yatin

Avatar photo
An experience full-stack engineer well versed with Core Java, Spring/Springboot, MVC, Security, AOP, Frontend (Angular & React), and cloud technologies (such as AWS, GCP, Jenkins, Docker, K8).

Longest Substring Without Repeating Characters

Hello. In this tutorial, we will implement an important data structure question known as finding the longest substring without repeating characters.

1. Introduction

The implementation will talk about three different areas i.e. –

  • Brute force method – Simplest approach to generate substrings having all unique characters from a given string and return the maximum length
  • Sliding window method – Increasing the performance of repeatable tasks to O(N^2)
  • Optimized sliding window method – Using the HashSet as a sliding window to reach the complexity of O(1)

2. Practice

Let us dive into some practice stuff from here and I am assuming that you already have Java 1.8 or greater installed on your local machine. I am using JetBrains IntelliJ IDEA as my preferred IDE. You’re free to choose the IDE of your choice.

2.1 Creating an implementation class

Create a java file that will show the implementation of the above 3 methods explained above. You’re free to change the code per your algorithm requirements.

Implementation class

package com.practice;

/*
 * jcg : category: core java
 * 1. brute force method
 * 2. sliding window method
 * 3. sliding window optimized
 */

class Bruteforce {

  // find all substrings of a string in a loop from start to end.
  // to check if the substring contains all unique characters put all characters in the set one by one.
  // if any character is present in the set, skip that string else consider its length.
  public long bruteforce(String str) {
    int n = str.length();
    int res = 0;

    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        if (checkRepetition(str, i, j)) {
          res = Math.max(res, j - i + 1);
        }
      }
    }
    return res;
  }

  private boolean checkRepetition(String s, int start, int end) {
    int[] chars = new int[128];

    for (int i = start; i <= end; i++) {
      char c = s.charAt(i);
      chars++;
      if (chars > 1) {
        return false;
      }
    }
    return true;
  }
}

class SlidingWindow {

  // in this approach we will skip the need of considering a substring and check if contains a
  // duplicate character. we will focus on improving the repeated tasks i.e. if the substring
  // from index to j-1 has already been checked to have no duplicate characters then simplify the
  // check if s[j] is a substring of s[i][j].
  public long slidingwindow(String str) {
    int n = str.length();
    int res = 0;

    for (int i = 0; i < n; i++) {
      boolean[] visited = new boolean[256];
      for (int j = i; j < n; j++) {
        if (visited[str.charAt(j)]) {
          break;
        } else {
          res = Math.max(res, j - i + 1);
          visited[str.charAt(j)] = true;
        }
      }
      visited[str.charAt(i)] = false;
    }
    return res;
  }
}

class OptimizedSlidingWindow {

  // in the sliding approach checking if the substring takes another string the complexity is o(n^2)
  // time. to improve it further we can use HashSet as a sliding window. here we check if a
  // character has already been visited and is present in a current window it can be done in o(1).
  // here we will use left and right pointers to keep a track of the maximum non-repeating substring
  // in a string.
  public long optimizedslidingwindow(String str) {
    int[] chars = new int[128];
    int left = 0;
    int right = 0;
    int res = 0;

    while (right < str.length()) {
      char r = str.charAt(right);
      chars[r]++;
      while (chars[r] > 1) {
        char l = str.charAt(left);
        chars[l]--;
        left++;
      }
      res = Math.max(res, right - left + 1);
      right++;
    }
    return res;
  }
}

public class LongestStringWithoutRepeatingCharactersEx {

  public static void main(String[] args) {
    Bruteforce bf = new Bruteforce();
    System.out.println("\nBruteforce method = " + bf.bruteforce("enjoyalgorithms"));

    SlidingWindow sd = new SlidingWindow();
    System.out.println("\nSlidingwindow method = " + sd.slidingwindow("enjoyalgorithms"));

    OptimizedSlidingWindow osd = new OptimizedSlidingWindow();
    System.out.println(
        "\nOptimizedslidingwindow method = " + osd.optimizedslidingwindow("enjoyalgorithms"));
  }
}

3. Demo

Run the file as a java file and if everything goes well the following logs will be shown on the IDE console.

Fig. 1: Console output

That is all for this tutorial and I hope the article served you with whatever you were looking for. Happy Learning and do not forget to share!

4. Summary

In this tutorial, we discussed the practical implementation to find the longest substring without repeating characters. You can download the source code from the Downloads section.

5. Download the Project

This was a tutorial to understand the practical implementation to find the longest substring without repeating characters.

Download
You can download the full source code of this example here: Longest Substring Without Repeating Characters

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

I have read and agree to the terms & conditions

 

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments