Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.Medium
{
 class LengthOfLongestSubstringSolution
 {
 public void execute()
 {
 int res = LengthOfLongestSubstring("abcabcbb");
 }
 public int LengthOfLongestSubstring(string s)
 {
 if (s=="")
 {
 return 0;
 }

 int max = 0;
 for (int i = 0; i < s.Length; i++)
 {
 int len = 1;
 var dict = new Dictionary<char, int>();
 dict.Add(s[i], 1);
 for (int j = i+1; j < s.Length; j++)
 {
 if (dict.ContainsKey(s[j]))
 {
 break;
 }
 else
 {
 len++;
 dict.Add(s[j], 1);
 }
 }
 if (max < len)
 {
 max = len;
 }
 }
 
 return max;
 }
 }
}

Time Complexity: O(n^2)

Space Complexity: O(n)

Using Sliding Window :

public int LengthOfLongestSubstringBySlidingWindow(string s)
 {
 int max = 0; 
 int start = 0;
 int end;
 var hashSet = new HashSet<char>();
 for (int i = 0; i < s.Length; i++)
 {
 if (hashSet.Contains(s[i]))
 { 
 while (s[start] != s[i])
 {
 hashSet.Remove(s[start]);
 start++;
 }
 start++;
 }
 else
 { 
 hashSet.Add(s[i]);
 if (max < hashSet.Count)
 {
 max = hashSet.Count;
 }
 }
 }
 return max;
 }

Time complexity: O(n)

Space complexity: O(n)