I was trying to solve a leetcode question but my solution is not returning the correct value for one of the test cases. I wanted to implement the two-pointer technique for this solution (if im using the technique wrong, advice is welcome on explaining the proper way to do it). The details are below:
Leetcode Question Title:
Longest Substring Without Repeating Characters.
Question:
Given a string, find the length of the longest substring without repeating characters. ( return int )
My Solution:
public int lengthOfLongestSubstring(String s) {
//place holder for me to create a "sub-string"
String sub = "";
//counter variable to count the characters in the substring
int count = 0;
int maxCount = 0;
//my attempt at a TWO POINTER TECHNIQUE
//pointers - to determine when the loop should break
int head = 0;
int tail = s.length();
//this variable was intended to be used with the "indexOf" method, as the "start from" index...
int index = 0;
while(head < tail){
//check if the next character in the string was already added to my substring.
int val = sub.indexOf(s.charAt(head), index);
//we proceed if it is -1 because this means the substring didnt previously contain that character
if(val == -1){
//added character to my substring
sub+= s.charAt(head);
count++;
head++;
} else {
//reset data to default conditions, while continuing at the "head index" and check the rest of the substring
count = 0;
sub = "";
}
//determine what the length of the longest substring.
maxCount = count > maxCount ? count : maxCount;
}
return maxCount;
}
I passed the test cases:
> "" = expect 0
> " " = expect 1
> "abcabcbb" = expect 3
> "bbbbb" = expect 1
> "pwwkew" = expect 3
> "aab" = expect 2
I failed test cases:
> "dvdgd" = expect 3, but got 2
> "dvjgdeds" = expect 5, but got 4
> "ddvbgdaeds" = expect 6, but got 4
Possible Issues:
I believe the issue occurred because it moves pass the index with "v", and then processes the substring "dg". So I attempted to change the solution, but fixing that issue caused all my other cases to return errors so I figured that attempt at a fix should be tossed out.
What I have also tried:
I also attempted to manipulate the "indexOf" method to change the start index, whenever the character was found in the string. This however generated an infinite loop.
I have been trying to solve this problem for a few hours and I am stomped. So any help would be appreciated greatly. And please be detailed with your explanation if you can, I am very new to DSA and programming, thank you greatly. If more information from me is needed, please let me know am I will try to answer.
Well, here you go:
public static int lengthOfLongestSubstring(String s) {
//place holder for me to create a "sub-string"
String sub = "";
//counter variable to count the characters in the substring
int count = 0;
int maxCount = 0;
//my attempt at a TWO POINTER TECHNIQUE
//pointers - to determine when the loop should break
int head = 0;
int tail = s.length();
//this variable shows where to start from
int index = 0;
while(head < tail){
//check if the next character in the string was already added to my substring.
int val = sub.indexOf(s.charAt(head)); //search whole substing
//we proceed if it is -1 because this means the substring didnt previously contain that character
if(val == -1){
//added character to my substring
sub+= s.charAt(head);
count++;
head++;
//determine what the length of the longest substring.
maxCount = count > maxCount ? count : maxCount;
System.out.println(sub); //let's see what we got so far
} else {
//reset data to default conditions, while continuing at the "head index" and check the rest of the substring
count = 0;
sub = "";
head=index+1; //begin from the next letter
index++; //move
}
}
return maxCount;
}