Move Zeroes - Leet Code Solution
Problem Statement Given an array nums, write a function to move all 0’s to the…
August 10, 2019
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Example 2:
Input: "bbbbb"
Output: 1
Example 3:
Input: "pwwkew"
Output: 3
As the question demands substring. Why not we find out what are the substrings out of the input strings first. Lookout for the steps:
You got the answer. Lets look at the code:
public class SimpleSolution {
private String str;
public SimpleSolution(String str) {
this.str = str;
}
private Set<String> getAllUniqueSubstrings() {
Set<String> res = new HashSet<>();
int l = this.str.length();
for (int i=0; i<l; i++) {
for (int j=i+1; j<l; j++) {
res.add(this.str.substring(i, j));
}
}
return res;
}
//Checks if the string is having unique characters
private boolean isUniqueChars(String substring) {
Set<Character> chars = new HashSet<>();
int l = substring.length();
for (int i=0; i<l; i++) {
if (chars.contains(substring.charAt(i))) {
return false;
}
chars.add(substring.charAt(i));
}
return true;
}
public String getResult() {
//Get all substrings
Set<String> substrings = this.getAllUniqueSubstrings();
//check their lengths, and return string with highest length
String result = null;
int maxLen = 0;
for (String substring : substrings) {
if (this.isUniqueChars(substring)) {
if (substring.length() > maxLen) {
result = substring;
maxLen = substring.length();
}
}
}
return result;
}
}
Overall complexity of this program is: O(n^2)
In above approach, our main time is in calculating substrings and checking if it has unique character. Lets have a look at the Sliding Window solution. We can maintain a HashSet to check if our substring has unique character or not. And, two variables for maintaining a sliding window.
Lets look at the code:
public class OptimizedSolution {
private String str;
public OptimizedSolution(String str) {
this.str = str;
}
public String getResult() {
int l = this.str.length();
Set<Character> set = new HashSet<>();
int i=0;
int j=0;
String maxStr = "";
while (i < l && j < l) {
if (!set.contains(this.str.charAt(j))) {
set.add(this.str.charAt(j));
j++;
String s = this.str.substring(i, j);
if (s.length() > maxStr.length()) {
maxStr = s;
}
}
else {
set.remove(this.str.charAt(i));
i++;
}
}
return maxStr;
}
}
Overall complexity of this program is: O(n) At the max, the program will run for O(2n) which is nearly equal to O(n)
In above approach, we are moving left side of sliding window one by one on encountering a duplicate character. Our objective is to move that left pointer of sliding window to the occurance of duplicate character plus 1.
Lets look at the code.
public class MoreOptimizedSolution {
private String str;
public MoreOptimizedSolution(String str) {
this.str = str;
}
public String getResult() {
Map<Character, Integer> map = new HashMap<>();
int l = this.str.length();
int i=0; int j=0;
String maxStr = "";
for (; j<l; j++) {
if (map.containsKey(this.str.charAt(j))) {
i = Math.max(map.get(this.str.charAt(j)), i);
}
if (j-i+1 > maxStr.length()) {
maxStr = this.str.substring(i, j+1);
}
map.put(this.str.charAt(j), j+1);
}
return maxStr;
}
}
The overall runtime of this code is: O(n), but is using extra space.
Problem Statement Given an array nums, write a function to move all 0’s to the…
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Problem Statement Roman numerals are represented by seven different symbols: I…
In this post, we will see some of the frequently used concepts/vocabulary in…
A Binary Search tree (BST) is a data structure which has two children nodes…
This is kind of preliminary technique of sorting. And, this is the first…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…