package dynamic;

import java.util.Arrays;

/**
 * 题目:求没有重复字符的最长子串(动态规划)
 * y: abcba 返回3
 * ddd 返回1
 *
 * @Author Gavin
 * @date 2021年12月27日 21:52
 */
public class solution_2 {
 //第一种方法:暴力破解法,时间复杂度O(n^3)

 /**
 * 第二种方法,滑动窗口思想
 * 思路:
 * 使用两个指针指向头部字符,然后其中一个向后移动,把每个字符记录到hash表里面,
 * 如果遇到某个字符已经存在与hash表中,就减去hash表中对应的这个值的值,然后移动另一个
 * 指针到下一个字符
 */
 //Time:O(n) Space:O(m)
 public static int solution_1(String s) {
 int[] counts = new int[256];//这里使用一个数组替代hash表
 int i = 0, j = 0, maxLen = 0;
 for (; i < s.length(); ++i) {
 //注意这里并不是双重for循环的时间复杂度
 //这里只有O(n)的复杂度,相当于就是把每个字符设置到数组里面了用了O(n),
 // 然后从数组取值用了O(1)
 for (; j < s.length(); ++j) {
 if (counts[s.charAt(j)] != 0) break;
 counts[s.charAt(j)] += 1;
 }
 maxLen = Math.max(maxLen, j - i);
 counts[s.charAt(i)] -= 1;
 }
 return maxLen;
 }

 /**
 * 第二种方法:比第一种效率高一些
 * 优化点就是i直接跳到重复字符的下一个位置开始重新计算长度,所以这就需要我们把每个
 * 字符所在的位置给记录下来。该方法和上面方法的主要区别就是该方法里面数组存储的是字符
 * 所在的下标位置。
 */
 public static int solution_2(String s) {
 int[] index = new int[256];
 Arrays.fill(index, -1);
 int maxLen = 0;
 for (int i = 0, j = 0; j < s.length(); ++j) {
 //定位i的位置,如果字符不重复那么i的位置就一直为0,如果遇到重复的了
 //就跳到重复位置的下一个位置(这个位置就是下面设置的)
 //这样的目的就是为了处理上面那种方法处理:
 // abcdc这样的情况(第一种方法在处理第二个c的时候还是会从bcdc开始处理
 // ,本方法就是直接处理第二个c位置了)
 i = Math.max(index[s.charAt(j)] + 1, i);
 maxLen = Math.max(maxLen, j - i + 1);
 //把字符和字符对应的下标位置存起来,用于i进行跳转
 index[s.charAt(j)] = j;
 }
 return maxLen;
 }

 //上面的方式不好理解,可以看这个方法理解。
 public static int solution_3(String s) {
 int[] index = new int[256];
 int maxLen = 0;
 for (int i = 0, j = 0; j < s.length(); ++j) {
 //取重复字符下标的后一位
 //i保存的的是重复字符下标大的位置,比如
 //abcdcb 当遇到c重复时候,i的下标值保存为2,然后遇到b重复,i本来正常应该是保存为1,但是重复字符
 //c的位置靠后,所以i仍然为2(因为你保存1没有用,中间还是存在c重复)
 if (index[s.charAt(j)] > i) {
 i = index[s.charAt(j)] + 1;
 }
 maxLen = Math.max(maxLen, j - i + 1);
 //把字符和字符对应的下标位置存起来,用于i进行跳转
 index[s.charAt(j)] = j;
 }
 return maxLen;
 }

 public static void main(String[] args) {
 System.out.println(solution_3("rewfdaadsfghjrtyueertgdfgd"));
 }
}