//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.

//

//

//

//

//

package com.llz.algorithm.algorithm2019.secondweek;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

public class LeetCode_3_2 {

/**

* Referenced from solution by using sliding window.

* Time complexity is O(n) and space complexity is O(n) (max value of n is the length of string).

*

* @param s

* @return

*/

public int lengthOfLongestSubstringBySW(String s) {

int maxLength = 0;

Set<Character> set = new HashSet<>();

int length = s.length();

int i = 0, j = 0;

while (i < length && j < length) {

if (!set.contains(s.charAt(j))) {

maxLength = Math.max(maxLength, j - i + 1);

set.add(s.charAt(j++));

} else

set.remove(s.charAt(i++));

}

return maxLength;

}

/**

* An optimised version of lengthOfLongestSubstringBySW by further reducing iteration times.

* Time complexity is O(n) and space complexity is O(n).

* <p>

* Watch the right boundary!

*

* @param s

* @return

*/

public int lengthOfLongestSubstringBySWOptimized(String s) {

Map<Character, Integer> map = new HashMap<>();

int maxLength = 0;

int length = s.length();

int i = 0, j = 0;

while (i < length && j < length) {

Character c = s.charAt(j);

if (map.containsKey(c)) {

i = Math.max(map.get(c) + 1, i);

}

map.put(c, j++);

maxLength = Math.max(maxLength, j - i);

}

return maxLength;

}

private int maxLength = 1;

/**

* Brutal Force

* Time complexity is O(n^3) and space complexity is O(n^3).

* Time Limit Exceed

*

* @param s

* @return

*/

public int lengthOfLongestSubstringByBrutalForce(String s) {

if (null == s || s.length() == 0)

return 0;

int length = s.length();

for (int i = 0; i < length; i++) {

for (int j = i + 1; j < length; j++)

checkSubStr(i, j, s);

}

return maxLength;

}

public void checkSubStr(int begin, int end, String s) {

Set<Character> set = new HashSet<>();

String subStr = s.substring(begin, end + 1);

for (int i = 0; i < subStr.length(); i++) {

if (set.contains(subStr.charAt(i)))

return;

else

set.add(subStr.charAt(i));

}

if (maxLength < (end - begin + 1))

maxLength = end - begin + 1;

}

public static void main(String[] args) {

LeetCode_3_2 l = new LeetCode_3_2();

System.out.println(l.lengthOfLongestSubstringBySWOptimized("tmmzuxt)"));

}

}