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