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
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 | 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
