Thought on longest Substring Without Repeating Characters problem
Problem statement: Given a string, find the longest substring without any repeating characters. For example, the input string is "abcabaa", then the longest substring is either "abc" or "bca" or "cab". Analysis: If we consider the string as an array of characters, one of the constraint of this problem is the substring -> it means the continuous sub-array of the array. Writing this into sub-problem, we are looking for pair of indices i,j in [0,n) where n is the length of the string, so that two conditions are satisfied: - there is no repeating character within indices i,j - (j - i + 1) is maximum (i.e. this is the length of the sub-string, assuming i <= j) Solution: Brute force: With these two conditions above, what we can do is: - as it is the sub-string, we can get all possible substring of the string - for each of the sub-string, find if it has repeating characters. In case it does not, get its length and compare with the current maxim...