0

I am attempting to do the longest substring without repeating characters problem in Java. I am trying to do two nested loop, and use a counter to keep track of how many characters are not repeated. When it finds a repeated character, it will reset the counter and break the loop. As of now, it is outputing 2 for this test case "abcabcbb", but I am not sure why.

class Solution { public int lengthOfLongestSubstring(String s) { if (s.length() == 0) return 0; if (s.length() == 1) return 1; int max = 1; // if (s.charAt(0) != s.charAt(1)) max = 2; int counter = 1; String a = "" + s.charAt(0); Character b; Character c; for (int i = 1;i<s.length()-1;i++){ b = s.charAt(i); for (int j = 0; j< s.length()-i; j++){ c = a.charAt(j); if (b.equals(c)){ counter = 1; a = "" + s.charAt(i); break; } else{ counter++; a = a + s.charAt(i); if (max < counter) max = counter; } } } return max; } }
Improve this question
0

2 Answers 2

Reset to default
1

As Jimmy points out, you do indeed miss even long runs of the same character as long as the run isn't of the character that starts the sequence you are testing. Here's a solution that I believe works in all cases:

public static int lengthOfLongestSubstring(String s) { if (s.length() == 0) return 0; if (s.length() == 1) return 1; int max = 0; for (int i = 0;i<s.length();i++){ Set<Character> chars = new HashSet<>(); chars.add(s.charAt(i)); for (int j = i+1; j< s.length(); j++){ Character b = s.charAt(j); if (chars.contains(b)) break; chars.add(b); } if (chars.size() > max) max = chars.size(); } return max; }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

It works. Thank you
There very well may be an optimization you could do here, as you're doing a lot of checking of the same characters over and over. Nothing came to mind though as I was putting this together.
Would you might upvoting this and checkmarking it as the answer to your question? - Oops. Just noticed that your question got closed :(. So maybe you can't do that.
1

The reason you are not getting the right answer here I believe is an algorithmic flaw. Your nested loops check to see if any character in a string is different from the first character. This does not check to see if there are any repeating characters in a substring. For example, in the example "abcabcbb," starting at the second 'a' there are no more 'a's, so your program will count the entire rest of the string. You will need to make some algorithmic modifications to solve your problem.

Improve this answer

1 Comment

Yeah, I realized it a bit later. Still I am stuck trying to make the loops check for the characters properly

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.