Monday, May 18, 2015

Longest Substring Without Repeating Characters

Problem Statement
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/
Programming Language: C#
Run Time Complexity: O(n)
Space Complexity: O(n)


Solution

public int LengthOfLongestSubstring(string s)
{
    if ((s == null) || (s.Length <= 0))
        return 0;    
    else if (s.Length == 1)
        return 1;

    // Dictionary to keep track of character and index position
    Dictionary<char, int> dictionary = new Dictionary<char, int>();
    int count = 0;
    int max_count = Int32.MinValue;
    int start_marker = 0;
    int end_marker = 0;
    

    while ((start_marker < s.Length) && (end_marker < s.Length))
    {
        if (!dictionary.ContainsKey(s[end_marker]))
        {
            dictionary.Add(s[end_marker], end_marker);
        }
        else if (dictionary.ContainsKey(s[end_marker]))
        {
            // Check if the index is in between start and end marker
            if ((dictionary[s[end_marker]] >= start_marker) && (dictionary[s[end_marker]] <= end_marker))
            {
                //update the count
                count = end_marker - start_marker;

                // update the max count
                max_count = Math.Max(count, max_count);

                // set the position of start marker
                start_marker = dictionary[s[end_marker]] + 1;
            }
            // Update with the current index
            dictionary[s[end_marker]] = end_marker;
        }
        end_marker++;
    }

    // for the end condition
    max_count = Math.Max(end_marker - start_marker, max_count);

    return max_count;
}

No comments:

Post a Comment