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.
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.
You can download the full source code of this example here: Longest Substring Without Repeating Characters
