Longest substring without repeating characters
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
import java.util.Set;
import java.util.HashSet;
class Main {
public static void main(String[] args) {
/**
* Problem:
* Given a string, find the length of the longest substring without repeating characters.
*
* Example:
* Input: "abcabcbb"
* Output: 3 (because "abc" is the longest substring without repeats)
*/
final String input = "abcabcbb";
// We need to find the longest substring without repeating characters
// I think we can use the two pointers approach with the same direction
// to traverse the string once
// We may have an index which is moving character by character (fast)
// Another index which is moving only when there is a repeated character.
// We can store the characters checked in a List to check if it was already validated
// We can also use a String to concatenate the characters and search for occurrences
// using the indexOf method of the String class
int slow = 0;
// The maxSubstringLength variable will contain the maximum substring length found
int maxSubstringLength = 0;
// Let's use the List to store the characters processed
Set<Character> charactersProcessed = new HashSet<>();
for (int fast = 0; fast < input.length(); fast++) {
// If the character in processing is present, we interrupt the substring and
// set the max length based on the charactersProcessed size only if the
// size is greater than maxSubstringLength
char characterInProcessing = input.charAt(fast);
if (charactersProcessed.contains(characterInProcessing)) {
if (charactersProcessed.size() > maxSubstringLength) {
maxSubstringLength = charactersProcessed.size();
}
charactersProcessed.clear();
}
charactersProcessed.add(characterInProcessing);
}
// I just noticed that I do not need two pointers given the charactersProcessed List
// The slow index could be useful if we check if the char is in the substring(slow, fast)
// I am not sure about the time complexity of searching a char over a String vs searching an
// element in a List
System.out.println(maxSubstringLength);
// I think it's better using a HashSet to avoid the time complexity of looking up
// elements in a List or the String with indexOf
}
}
Java
INFO