LeetCode Problem
Given a string s, find the length of the longest substring without repeating characters.
Solution
This problem is easy to understand, but not that easy to find out the solution ( Acceptance rate – 33.5% )
Now, let us see how we find out the solution.
C# Solution
Solution1 – List
public class Solution {
public int LengthOfLongestSubstring(string s) {
if(string.IsNullOrEmpty(s))
{
return 0;
}
List<char>list = new List<char>();
int max = 0;
for(int i = 0;i<s.Length;i++)
{
char tmp = s[i];
if(!list.Contains(tmp))
{
list.Add(tmp);
}
else
{
max = Math.Max(max,list.Count); //check the max number
int ii = list.IndexOf(tmp);
list.RemoveRange(0,ii+1);
list.Add(tmp);
}
}
if(list.Count != 0)
{
max = Math.Max(max,list.Count);
}
return max;
}
}Runtime : 67ms、82ms、62ms
The first solution used list to store the characters.
And in each iteration, we will check if this character already exists in the list. If it exists, we will update the max number and remove some elements in the list ( index<= the index of the character in the list ).
Solution2 – HashSet + two pointers
public class Solution {
public int LengthOfLongestSubstring(string s) {
if(string.IsNullOrEmpty(s))
{
return 0;
}
HashSet<char> hSet = new HashSet<char>();
int max = 0;
int i = 0;
int j = 0;
while(i<s.Length)
{
if(!hSet.Contains(s[i]))
{
hSet.Add(s[i]);
i++;
}
else
{
max = Math.Max(max,hSet.Count);
hSet.Remove(s[j]);
j++;
}
}
max = Math.Max(max,hSet.Count);
return max;
}
}Runtime : 143ms、67ms、92ms
In the second solution, we use HashSet to store the value and use two integer variables as pointers.
Solution3 – Dictionary
public class Solution {
public int LengthOfLongestSubstring(string s) {
Dictionary<char,int> dict = new Dictionary<char,int>();
int max = 0;
for (int i = 0;i < s.Length;i++)
{
char c = s[i];
if (!dict.ContainsKey(c))
{
dict.Add(c, i);
max = Math.Max(dict.Count, max);
}
else
{
i = dict[c] ;
dict.Clear();
}
}
return max;
}
}In this solution, we use dictionary’s function – 【ContainsKey】 to check if the character exists or not.
If it didn’t exist, we will add it to the dict and check the max, than go to next iteration of loop.
And if it exist, we will reset i to the last index it appeared, and iterate again.
Runtime : 144ms、114ms、126ms
Java Solution
Solution1
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.isEmpty())
{
return 0;
}
ArrayList<Character>list = new ArrayList<Character>();
int max = 0;
for(int i = 0;i<s.length();i++)
{
char tmp = s.charAt(i);
if(!list.contains(tmp))
{
list.add(tmp);
}
else
{
max = Math.max(max,list.size()); //check the max number
int ii = list.indexOf(tmp);
//list.removeRange(0,ii+1);
list.subList(0,ii+1).clear();
list.add(tmp);
}
}
if(list.size() != 0)
{
max = Math.max(max,list.size());
}
return max;
}
}Runtime : 11ms、7ms、10ms
Solution2
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.isEmpty())
{
return 0;
}
HashSet<Character> hSet = new HashSet<Character>();
int max = 0;
int i = 0;
int j = 0;
while(i<s.length())
{
if(!hSet.contains(s.charAt(i)))
{
hSet.add(s.charAt(i));
i++;
max = Math.max(max,hSet.size());
}
else
{
//max = Math.max(max,hSet.size());
hSet.remove(s.charAt(j));
j++;
}
}
//max = Math.max(max,hSet.size());
return max;
}
}Runtime : 12ms、7ms、13ms
Python3 Solution
Solution1
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if s == '':
return 0;
list1 = [];
m = 0;
for i in range(0,len(s)):
tmp = s[i]
if(tmp not in list1):
list1.append(tmp);
else:
m = max(m,len(list1));
i = list1.index(tmp);
list1 = list1[i+1:];
list1.append(tmp);
if(len(list1)>0):
m = max(m,len(list1));
return m;Runtime : 123ms、109ms、146ms ≈ faster than 40%
That is unsatisfactory, maybe we need to find a faster solution.
⭐Solution2
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if s == '':
return 0;
l = set();
m = 0;
i = 0;
j = 0;
while(i<len(s)):
if(s[i] not in l):
l.add(s[i])
i+=1
else:
m = max(m,len(l));
l.remove(s[j])
j+=1
m = max(m,len(l));
return m;Runtime : 74ms、92ms、78ms
That is much better than solution1 !!!
JavaScript Solution
Solution1
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var mySet = new Set();
var max = 0;
var i = 0;
var j = 0;
while(i<s.length)
{
if(!mySet.has(s[i]))
{
mySet.add(s[i]);
i++;
}
else
{
max = Math.max(max,mySet.size);
mySet.delete(s[j]);
j++;
}
}
max = Math.max(max,mySet.size);
return max;
};Runtime : 117ms、87ms、98ms
Submission Detail
C#
Java
Python3
JavaScript
Conclusion
🧡If my solution helps, that is my honor!
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
The problem link : Longest Substring Without Repeating Characters – LeetCode
Latest Post