Longest Substring Without Repeating Characters Simple Solution in C# and Java

Hello Friends, This is a very interesting problem I have encountered while solving some data structures and also problems. The problem statement is “Given a string, find the length of the longest substring without repeating characters.”

Longest Substring Without Repeating Characters

First lets see with the help of example what does this actually mean:

Example 1:

Input: "aa"
Output: 1
Explanation: The answer is "a", with the length of 1. 

Example 2:
Input: "ab" 
Output: 2 
Explanation: The answer is "ab", with the length of 2.

Example 2:
Input: "aba"
Output: 2
Explanation: The answer is "ab", with the length of 2.

Example 2:
Input: "abac"
Output: 3
Explanation: The answer is "bac", with the length of 3.

I messed up many times before solving this problem. I used many solution but I was not able to come up with optimal solution which can cover all the scenarios.

Finally I arrived at the solution explained and covered in the below Java code:

 public int lenghtOfLongestSubStringRefined(String s) {
	 char[] inputStringAsCharArray = s.toCharArray();
	 ArrayList<Character> longestSubString = new ArrayList<Character>();
	 int longestSubStringValue = 0;
	 for (char c : inputStringAsCharArray) {
		if(!longestSubString.contains(c)) {
			longestSubString.add(c);				
		}
		else {
			int indexOfFoundChar = longestSubString.indexOf(c);
			longestSubString = new ArrayList<Character>(longestSubString.subList(indexOfFoundChar + 1, longestSubString.size()));
			longestSubString.add(c);
							
		}
		
		longestSubStringValue = longestSubStringValue < longestSubString.size() ? longestSubString.size():	longestSubStringValue++;
	}
	 
	return longestSubStringValue;
 }

And the C# code looks much cleaner thanks to some LINQ methods

public int LenghtOfLongestSubStringRefined(String s)
{
    char[] inputStringAsCharArray = s.ToCharArray();
    IList<char> longestSubString = new List<char>();
    int longestSubStringValue = 0;
    foreach (char c in inputStringAsCharArray)
    {
        if (!longestSubString.Contains(c))
        {
            longestSubString.Add(c);
        }
        else
        {
            int indexOfFoundChar = longestSubString.IndexOf(c);
            longestSubString = longestSubString.Skip(indexOfFoundChar + 1).ToList();
            longestSubString.Add(c);

        }

        longestSubStringValue = longestSubStringValue < longestSubString.Count ? longestSubString.Count : longestSubStringValue++;
    }

    return longestSubStringValue;
}

Explanation:

The explanation is quite simple, we have to carry an alternate array which will keep the longest sub string while traversing the original string.

If we encounter an character which is already there in the longest sub string array, we get the position of the character. Finally taking out the sub array out of it from the index of found character.

And in each iteration we will keep the count of the elements in the alternate array. If the count is greater than the already existing count we will update it otherwise we keep it same.

This question is an simple example of how we can solve the array problems using an alternate array. Though it is bit expensive on the memory usage but there is no need to maintain two pointers.

Top career enhancing courses you can't miss

My Learning Resource

Excel your system design interview