Sometimes it's helpful to remain in the problem domain as much as possible. This approach creates a solution before any thought of coding. This approach leaves us with a set of minimally complex logical operations which then require implementation.
First our initial condition. Columns should be clear: Input (always same), Current (the current substring without repeating characters), Answer (the current answer in String form) and Logic (what logic is applied for this step:
So first iteration starts the same as rest : get next character in Input. Check if it is in the Current substring and since it is not add to Current. Here we also ask the question: Is Answer shorter than Current and if so set Answer to Current.
Note in the Logic column we are developing operations which we'll need to implement in the solution.
Repeat for second character input (no new operations):
And again for third - (no new operations):
Ok now we find next CH in the current substring so we need a new operation: 'Remove chars in current up to but not including CH. Note that "add CH to current" is done in this case as well. Note also some new logic (answer was as long or longer than current so "Do Nothing").
And finish things out - no new operations.
So now we reach the end of input and simply ask the question "How long is the Answer" and that is the result.
So now looking at the Logic column we see operations to perform:
// Initial condition
String answer = "";
String current = "";
Let's work completely in Strings to keep things simple - optimization can come later..
Let's define the "next CH (nextChar)" operation:
// Get the ith character (0-based) from 's' as a String.
private static String nextChar(String s, int i) {}
We'll need an operation which "checks if 'Current contains CH'":
// Does the 'current' String contain the 'nextChar' String?
private static boolean currentContainsCh(String current, String nextChar) {}
We'll need to check if current Answer is shorter than Current:
// True if the 'answer' String is short in length than the 'current' string.
private static boolean isAnswerShorterThanCurrent(String current, String answer) {}
And the ability to append the nextChar to Current:
// Append the 'nextChar' to the 'current' String and return the String.
private static String addChToCurrent(String current, String nextChar) {}
And finally the ability to remove all characters up to but not including current char in Current:
// @return a String which has all characters removed from 'current' up to but not including 'ch'
private static String removeUpToChar(String current, String ch) {}
So putting it all together (essentially still in the problem domain since we haven't implemented any operations but just projected the problem into structure):
public int lengthOfLongestSubstring(String s) {
String answer = "";
String current = "";
for (int i = 0; i < s.length(); i++) {
String nextChar = nextChar(s,i);
if (currentContainsCh(current, nextChar)) {
current = removeUpToChar(current, nextChar);
}
current = addChToCurrent(current,nextChar);
if (isAnswerShorterThanCurrent(current,answer)) {
answer = new String(current);
}
}
return answer.length();
}
And now implementing the "operations" becomes easier (and fun) since they are isolated and not complex. This is left for you. When implemented it passes the problem.
The next logical step after verifying correctness is to consider optimizations - if needed.
