Showing posts from August, 2018

Sliding Window Approach and Azure Functions

Saw this problem being asked by an interviewer recently: Given a (long) string, write an algorithm to return the longest contiguous sequence with non-repeating characters One approach to solving this problem requires a N^3 time-complexity: generate all the sequences (N^2) and for each one check whether it only contains unique characters (N), keeping track of the longest one. It would be something like this: static string LongestSequenceWithUniqueCharsSlow(string str) { if (String.IsNullOrEmpty(str)) return str; string max = ""; for (int i = 0; i < str.Length; i++) { for (int j = i; j < str.Length; j++) { string candidate = str.Substring(i, j - i + 1); if (ContainsUniqueChars(candidate) && candidate.Length > max.Length) { max = candidate; } } } return max; } static bool ContainsUniqueChars(string str) { Hashtable mark = new Hashtable(); for (int i = 0; i < str.Length; i++) { if (mark.ContainsKe