Longest Substring Without Repeating Characters - Need to Understand the Algorithm for given C# Solution

Question

Problem: Longest Substring Without Repeating Characters.

I have this solution. But I do not have much of theoretical knowledge about DSA. Trying to understand which algorithm it comes under and will it be efficient than 'Sliding Window' approach. Per my understanding the time complexity is o(n). What will be the space complexity? Any help/guidance will be appreciated. Thanks!

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        
        List<char> list = new List<char>();
        int output = 0;
        
        foreach(char c in s)
        {
            if(list.Contains(c))
            {
                if(list.Count > output)
                    output=list.Count;
                int index = list.IndexOf(c);
                list.RemoveRange(0,index+1);
                list.Add(c);
            }
            else
            {
                list.Add(c);
            }
        }
        
        return list.Count > output ? list.Count : output;
    }
}

Answer 1

Memory complexity of you solution is O(a) (I'm not counting in the s string size - in ideal situation in could be a generator) and pessimistic time complexity is O(a*n) where:

n - length of the s input string

a - alphabet size |A|

For s repeating whole alphabet multiple times:

s = "abcd...xyzabcd...xyzabcd...xyz"

After first a iterations the list size is a and it contains every letter.

Then for each consecutive iteration we remove first element, which means all elements have to shift - the cost of this operation is a-1.

We end up with O((n-a) * (a-1)) = O(a * n).

The solution could be to use LinkedList, but as @maraca mentioned in the comment - Contains pessimistic complexity is also O(L) where L is list length and we again get O(a * n) for s that rarely empties the list.

How to get real O(n)?

As comment suggest use HashMap to store on what index the element was last seen. Update the indexes as you process the array. Calculate the output as difference between current position and last seen index (if it's less than current length).

You could also say, that for a-z alphabet the constant of hashing algorithm is bigger than a (24) and either way it's O(n). Requires testing times for real world examples :D