Longest SubString Without Repeating Characters LeetCode
Way 1 : Using ArrayDeque and ArrayList
int count=0;
int index=0;
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayDeque<Character> arr=new ArrayDeque<Character>();
for(int i=0;i<s.length();i++){
if(arr.contains(s.charAt(i))){
aa.add(count);
count=0;
arr.clear();
i=index++;
}
else{
arr.addLast(s.charAt(i));
count++;
}
}
aa.add(arr.size());
return Collections.max(aa);
APPROACH:
Here we will add the elements of string one by one in ArrayDeque and will increase the value of count simultaneously. If an element exists prior in the deque then we will store the value of count up to that element in ArrayList and empty or clear the array deque. Now our iteration starts from the next element which means now we will start from the second element.
Iteration starts from the second element in a manner that we have formed the largest substring from the first element and now we will see the largest substring from the second element and so on...
We will return the max value from ArrayList which actually stores the length of substrings.
TIME:O(N) [ArrayDeque takes a good amount of time but since we will be traversing the same string but from different indexes and at different times. Overall Time is O(N)][LeetCode Time: 623ms faster than 5.02%]
SPACE:O(1) [ArrayDeque and ArrayList occupies space][LeetCode Memory: 38.7 less than 95.97%]
=======================================================================
Way 2: Using ArrayDeque and HashSet
int count=0;
int index=0;
HashSet<Integer>aa=new HashSet<Integer>();
ArrayDeque<Character> arr=new ArrayDeque<Character>();
for(int i=0;i<s.length();i++){
if(arr.contains(s.charAt(i))){
aa.add(count);
count=0;
arr.clear();
i=index++;
}
else{
arr.addLast(s.charAt(i));
count++;
}
}
aa.add(arr.size());
return Collections.max(aa);
TIME:O(N) [LeetCode Time: 608ms faster than 5.03%]
SPACE:O(1) [LeetCode Memory: 39.2 less than 54.38%]
=========================================================================
Way 3: Using Stack and ArrayList
int count=0;
ArrayList<Integer>aa=new ArrayList<Integer>();
Stack<Character>stack=new Stack<Character>();
int index=0;
if(s.isEmpty()){
// System.out.println(0);
return 0;
}
else if(s.length()==1){
//System.out.println(1);
return 1;
}
else{
for(int i=0;i<s.length();i++){
if(stack.isEmpty()){
// System.out.println("Empty stack push character is: "+s.charAt(i));
stack.push(s.charAt(i));
count++;
}
else{
if(!stack.contains(s.charAt(i))){
//System.out.println("Not contained in stack push character is: "+s.charAt(i));
stack.push(s.charAt(i));
count++;
}
else{
//int a=stack.indexOf(s.charAt(i));
aa.add(count);
count=0;
stack.clear();
i=index++;
// System.out.println("a value is :"+a);
// System.out.println("i value is :"+i);
}
}
}
}
aa.add(stack.size());
//System.out.println(aa+" ");
//System.out.println(Collections.max(aa));
return Collections.max(aa);
TIME:O(N) [LeetCode Time: 606ms faster than 5.03%]
SPACE:O(1) [LeetCode Memory: 39.3 less than 45.52%]
=========================================================================
Way 4: Using Stack and HashSet
int count=0;
HashSet<Integer>aa=new HashSet<Integer>();
Stack<Character>stack=new Stack<Character>();
int index=0;
if(s.isEmpty()){
// System.out.println(0);
return 0;
}
else if(s.length()==1){
//System.out.println(1);
return 1;
}
else{
for(int i=0;i<s.length();i++){
if(stack.isEmpty()){
// System.out.println("Empty stack push character is: "+s.charAt(i));
stack.push(s.charAt(i));
count++;
}
else{
if(!stack.contains(s.charAt(i))){
//System.out.println("Not contained in stack push character is: "+s.charAt(i));
stack.push(s.charAt(i));
count++;
}
else{
//int a=stack.indexOf(s.charAt(i));
aa.add(count);
count=0;
stack.clear();
i=index++;
// System.out.println("a value is :"+a);
// System.out.println("i value is :"+i);
}
}
}
}
aa.add(stack.size());
//System.out.println(aa+" ");
//System.out.println(Collections.max(aa));
return Collections.max(aa);
TIME:O(N) [LeetCode Time: 645ms faster than 5.03%]
SPACE:O(1) [LeetCode Memory: 39.1 less than 75.19%]
Thanks for Reading.😇
Comments
Post a Comment