Longest Substring Without Repeating Characters – Leetcode #3

Problem Statement

This problem is from Leetcode – Longest Substring Without Repeating Characters. The problem statement is as below:

Given a string s, find the length of the longest substring without repeating characters.

Solution

Approach – 1

1. Initialize a string curStr to empty string. This is where we’ll store the sub-strings as we move forward.
2. Initialize the re-start index to zero. We’ll use this to move our sub-string window to the right.
3. Iterate through the given string in a for loop.
4. If the current char is not part of curStr, then append to it. This is where we are searching for the sub-string with all unique chars.
5. If the current char is part of curStr, then we need to move our search window to the right:
   • Re-initialize curStr to an empty string and
   • update the for loop index with re-start index.
   • increment the re-start index.

As the window is moving right, keep computing max sub-string length in a max variable. When the for loop exits, the max variable is our answer. See the code sample below:

public int lengthOfLongestSubstring(String input) {
		
		// if input is empty then return 0
		if(input.equals("")) {

			return 0;
		}
		
		int maxx = 1;
		
		// index from where we need to re-start the for loop
		int reStartIdx = 0;
		
		// this is where we'll store the sub-strings
		String curStr = "";
		
		int count = 1;
		
		// iterate till last input char
		for(int i=0; i<input.length(); i++) {
			
			// read the current char
			char nextChar = input.charAt(i);
			
			// if curStr doesn't contain this char
			if(curStr.indexOf(nextChar) == -1) { 
				
				// append to curStr
				curStr = curStr + input.charAt(i);
				
				// update count with sub-string length
				count = curStr.length();
				
				// compare with a max variable and update
				if(count > maxx) {
					
					// this ensures that maxx always contains our answer
					maxx = count;

				}
			}
			
			// if curStr contains this char
			else if (curStr.indexOf(nextChar) != -1) {
				
				// re-initialize the curStr to empty string
				curStr = "";
				
				// update the for loop index with new index and go back in the loop 
				i=reStartIdx;
				
				// update re-start index for next time
				reStartIdx++;

			}
		}

		return maxx;
	}

You can checkout the code from Github here: Longest substring – First Approach. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	287 ms | Beats 5.02 %
MEMORY	45.83 MB | Beats 5.31 %
TIME COMPLEXITY	O (N)

Approach – 2

Lets try to improve on the above performance by using a Hashmap that stores the characters and their updated occurrence.

1. Initialize the left and the right indices to zero. This controls our sliding window.
2. Iterate in a while loop. Check if the incoming char exists in Hashmap or not. If it doesn’t exist, then add to the Hashmap with its position.
3. If it already exists in the Hashmap then we need to update our window:
   • check if the position of current char is greater than left index.
   • if yes then increment the left char.
4. Compare the max variable with window length and take the greater length and store back in max.
5. Increment the right window forward.

See the code sample below:

public int lengthOfLongestSubstring(String input) {

		// if input is empty then return 0
		if(input.equals("")) {

			return 0;
		}
		
		// Map that stores char and its latest occurrence
		Map<Character, Integer> charMap = new HashMap<>();
		int len = input.length();
		
		// right index 
		int right = 0;
		
		// left index
		int left = 0;
		
		// sub-string length
		int max = 0;
		
		// while right index is less that input length
		while (right < len ) {
			
			// if map contains current char
			if (charMap.containsKey(input.charAt(right)) ) {
				
				// then update left index
				if(charMap.get(input.charAt(right)) >= left) {
					
					left = charMap.get(input.charAt(right)) + 1;
				}
				
			} // end if
			
			// else if map doesn't contain current char
			charMap.put(input.charAt(right), right);
			
			// compare max with window length and update
			max = Math.max(max, right - left + 1);
			
			// increment right index
			right++;
			
		} // end while

		return max;
	}

You can checkout the code from Github here – Longest substring – Second Approach. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	5 ms | Beats 85.76 %
MEMORY	44.54 MB | Beats 46.17 %
TIME COMPLEXITY	O (N)

Approach – 3

Lets try to further improve on the approach above. Notice that the function call input.charAt(right) can also be used to get the ASCII value of the char it is returning. We’ll use this feature to use an int array instead of Hashmap.

1. Declare an int array with length 128 to store all ASCII chars.
2. Initialize this array with -1
3. We’ll update this array with the latest occurrence of current char while moving the window forward.

See the code sample below:

public int lengthOfLongestSubstring(String input) {

		// if input is empty then return 0
		if(input.equals("")) {

			return 0;
		}
		
		// declare int array with length to store all ASCII chars
		int[] charIndex = new int[128];
		
		// initialize with -1
		Arrays.fill(charIndex, -1);

		int len = input.length();

		// right index 
		int right = 0;

		// left index
		int left = 0;

		// sub-string length
		int max = 0;

		// while right index is less that input length
		while (right < len ) {

			if (charIndex[input.charAt(right)] >= left) {

				 left = charIndex[input.charAt(right)] + 1;			

			} // end if

			charIndex[input.charAt(right)] = right;
            max = Math.max(max, right - left + 1);

			// increment right index
			right++;

		} // end while

		return max;
	}

You can checkout the code from Github here: Longest Substring – Third Approach. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	2 ms | Beats 98.91 %
MEMORY	42.91 MB | Beats 94.39 %
TIME COMPLEXITY	O (N)