Longest substring without repeating characters java

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

• 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.

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 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.

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

Источник

Find the Longest Substring Without Repeating Characters

As always, the writeup is super practical and based on a simple application that can work with documents with a mix of encrypted and unencrypted fields.

We rely on other people’s code in our own work. Every day.

It might be the language you’re writing in, the framework you’re building on, or some esoteric piece of software that does one thing so well you never found the need to implement it yourself.

The problem is, of course, when things fall apart in production — debugging the implementation of a 3rd party library you have no intimate knowledge of is, to say the least, tricky.

Lightrun is a new kind of debugger.

It’s one geared specifically towards real-life production environments. Using Lightrun, you can drill down into running applications, including 3rd party dependencies, with real-time logs, snapshots, and metrics.

Learn more in this quick, 5-minute Lightrun tutorial:

Slow MySQL query performance is all too common. Of course it is. A good way to go is, naturally, a dedicated profiler that actually understands the ins and outs of MySQL.

The Jet Profiler was built for MySQL only, so it can do things like real-time query performance, focus on most used tables or most frequent queries, quickly identify performance issues and basically help you optimize your queries.

Critically, it has very minimal impact on your server’s performance, with most of the profiling work done separately — so it needs no server changes, agents or separate services.

Basically, you install the desktop application, connect to your MySQL server, hit the record button, and you’ll have results within minutes:

DbSchema is a super-flexible database designer, which can take you from designing the DB with your team all the way to safely deploying the schema.

The way it does all of that is by using a design model, a database-independent image of the schema, which can be shared in a team using GIT and compared or deployed on to any database.

And, of course, it can be heavily visual, allowing you to interact with the database using diagrams, visually compose queries, explore the data, generate random data, import data or build HTML5 database reports.

Источник

LeetCode #3 — Longest Substring Without Repeating Characters

Hey happy folks 👋! It’s a brand new day and it’s time to look at another problem from LeetCode — Longest Substring Without Repeating Characters.

Given a string s , find the length of the longest substring without repeating characters.

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

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

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

The input will be a string containing characters which may or may not be repeated. The ask is to find the longest substring (a part of the given string) having all distinct characters.

One characteristic of a substring is that all the characters are contiguous. For e.g, in a given string s = redquark , the valid substrings are — edq , ar , red , quar etc. The substrings rd , qur are not valid substrings because even though they contain characters from the source strings, those characters are not continuous.

Apart from above, we are given constraints on the size of string and the characters that are present in a string.

There can be many substrings as outputs but we have to return only the longest among them.

From the input, we can gather the following information —

1. Given data structure is a string which is a linear data structure.
2. The output must be a substring — a part of the given string.
3. Naive solution is to check for each combination of characters in the string

Are you thinking what I am thinking 🤔? Yes, this is a classic example of a problem that can be solved using the legendary technique — Sliding Window Algorithm.

Following are the steps that we will follow —

1. Have two pointers which will define the starting index start and ending index end of the current window. Both will be 0 at the beginning.
2. Declare a Set that will store all the unique characters that we have encountered.
3. Declare a variable maxLength that will keep track of the length of the longest valid substring.
4. Scan the string from left to right one character at a time.
5. If the character has not encountered before i.e., not present in the Set the we will add it and increment the end index. The maxLength will be the maximum of Set.size() and existing maxLength .
6. If the character has encounter before, i.e., present in the Set , we will increment the start and we will remove the character at start index of the string.
7. Steps #5 and #6 are moving the window.
8. After the loop terminates, return maxLength .

We are scanning the string from left to right only once, hence the time complexity will be O(n).

We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

The problem clearly states that the string contains only English letters, digits, symbols and spaces and are covered in 256 code points. Therefore, a string will be made up of a combination of these characters.

Since a Set can contain only unique elements, at any point the size of Set cannot be more than 256.

What does this mean? This means that the size of set is a function independent of the size of the input. It is a constant. Therefore, the space complexity will be O(1) (let me know in comments if you think otherwise).

After analyzing and deciding on the approach, it’s time to write some code —

package org.redquark.tutorials.leetcode; import java.util.HashSet; import java.util.Set; public class LongestSubstringWithoutRepeatingCharacters  public int lengthOfLongestSubstring(String s)  // Base condition if (s == null || s.equals(""))  return 0; > // Starting window index int start = 0; // Ending window index int end = 0; // Maximum length of substring int maxLength = 0; // This set will store the unique characters SetCharacter> uniqueCharacters = new HashSet>(); // Loop for each character in the string while (end  s.length())  if (uniqueCharacters.add(s.charAt(end)))  end++; maxLength = Math.max(maxLength, uniqueCharacters.size()); > else  uniqueCharacters.remove(s.charAt(start)); start++; > > return maxLength; > >

def lengthOfLongestSubstring(s: str) -> int: # Base condition if s == "": return 0 # Starting index of window start = 0 # Ending index of window end = 0 # Maximum length of substring without repeating characters maxLength = 0 # Set to store unique characters unique_characters = set() # Loop for each character in the string while end  len(s): if s[end] not in unique_characters: unique_characters.add(s[end]) end += 1 maxLength = max(maxLength, len(unique_characters)) else: unique_characters.remove(s[start]) start += 1 return maxLength

var lengthOfLongestSubstring = function (s)  // Base condition if (!s)  return 0; > // Starting index of the window let start = 0; // Ending index of the window let end = 0; // Maximum length of the substring let maxLength = 0; // Set to store the unique characters const uniqueCharacters = new Set(); // Loop for each character in the string while (end  s.length)  if (!uniqueCharacters.has(s[end]))  uniqueCharacters.add(s[end]); end++; maxLength = Math.max(maxLength, uniqueCharacters.size); > else  uniqueCharacters.delete(s[start]); start++; > > return maxLength; >;

fun lengthOfLongestSubstring(s: String): Int  // Base condition if (s == "")  return 0 > // Starting window index var start = 0 // Ending window index var end = 0 // Maximum length of substring var maxLength = 0 // This set will store the unique characters val uniqueCharacters: MutableSetChar> = HashSet() // Loop for each character in the string while (end  s.length)  if (uniqueCharacters.add(s[end]))  end++ maxLength = maxLength.coerceAtLeast(uniqueCharacters.size) > else  uniqueCharacters.remove(s[start]) start++ > > return maxLength >

That’s all folks! In this post, we solved LeetCode problem #3 using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!

Источник

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

The output string is “abc”, with a length of 3.

The longest substring in this example is “b”. Its length is 1.

The answer is “wke”. Its length is 3.

In this tutorial, I am going to discuss how we can solve this problem efficiently using a sliding window approach and it’s java code. At the end of this tutorial, I have mentioned the link of the video tutorial.

Let’s first see the brute force approach to solve this problem. The simplest approach is to form all the possible substrings and track the length of the longest substring with unique characters.

The time complexity of this approach is O(n^3).

Longest Substring Without Repeating Characters using Sliding Window – Java Code

Let’s improve our previous solution. In this example, I am going to explain how to find the length of longest non-repeating substring using sliding window approach.

The idea here is to maintain a window of unique character. Each window has start and end index, based on that we know the window size.To check unique character in a window, i am using set data structure. Set does not allow duplicate values and also the lookup time is O(1).

Here are the following steps to solve this problem –

• Declare two indexes i and j and initialize with zero. Variable i indicate index of the start window and j indicate end index.

• Traverse a string and pick one character at a time.
• First check, if a character exists in a set. If it doesn’t exist in a set then add them in a set and increment the count of j and the index of i remain as it is. Also, keep track of the length of a window.
• If character exists in a set then remove the character from a set and increment the count of i until all the characters in a window is unique again.
• Repeat this step until the string is traversed completely.

The time complexity of this approach is O(n) and it’s space complexity is also O(n).

Источник