【Leetcode】395. Longest Substring with At Least K Repeating Characters

タイトルリンク:https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
タイトル:
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

考え方:
1.最初からスキャンを開始し、最初の条件を満たすサブストリングに遭遇した場合、setでそのサブストリングの文字種類を記録し、そのサブストリングの長さを記録する.このとき文字列はすでに1段1段に分割されており、ある段の末尾文字の下にiと表記すると、sets[i]はiを末尾とするサブ列の文字セットを表し、len[i]はその列の長さを表す.このときset配列の各set要素には3つの状態があり、nullはその文字が有効文字列にあることを示し、set長が0はその文字から始まるサブ列が条件に合致していないことを示すので、setは0であり、区切り記号とすることができ、set長が0より大きいと、現在の文字を末尾とする有効サブ列が存在する.
2.次は、これらのセグメントのサブストリングやセパレータをマージすることを考えます.マージするときは、前のサブストリングの文字セットだけでなく、前のサブストリングの長さも知る必要があるので、set、len配列を設定しました.set配列をスキャンし、現在setが0であれば、その文字が前のセグメントとサブ列を構成するか否かを判断する.現在のsetが0でない場合は、サブストリングと前のセグメントストリングまたはセパレータを直接接続します.
時間オーバーヘッドは主に分割サブ列にあり,時間複雑度はO(n^2),空間複雑度はO(n)である.コードはさらに簡略化できます.
アルゴリズム:

	public int longestSubstring(String s, int k) {
		if (s.length() < k)
			return 0;
		int max = 0;
		HashSet[] sets = new HashSet[s.length()];
		int len[] = new int[s.length()];//       
		//      ： null                 ；
		// size 0 set                           
		// size  0，                        

		//   
		for (int i = 0; i < s.length(); i++) {
			int map[] = new int[26];
			boolean flag2 = false;//  i  ，       2       
			for (int j = i; j < s.length(); j++) {
				map[s.charAt(j) - 'a']++;

				boolean flag = true;// i~j       
				for (int m : map) {
					if (m > 0 && m < k) {
						flag = false;
					}
				}

				if (flag) {//  i~j      ，        set ，         
					sets[j] = new HashSet();
					for (int kk = 0; kk < map.length; kk++) {
						if (map[kk] != 0) {
							sets[j].add((char) (kk + 'a'));
							len[j] += map[kk];
						}
					}
					i = j;
					flag2 = true;//        
					break;
				}
			}
			if (flag2 == false) {//            ， i       （i~s.length          ）
				sets[i] = new HashSet();
			}

		}

		int pre = 0;//             
		for (int i = 0; i < s.length(); i++) {
			if (sets[i] != null) {
				pre = i;
				break;
			}
		}

		//   
		for (int i = pre + 1; i < s.length(); i++) {
			if (sets[i] != null) {
				if (sets[i].size() == 0 && sets[pre].size() != 0 && sets[pre].contains(s.charAt(i))) {
					sets[i].addAll(sets[pre]);
					len[i] = len[pre] + 1;
				} else if (sets[i].size() != 0 && sets[pre].size() != 0) {
					sets[i].addAll(sets[pre]);
					len[i] += len[pre];
				}
				pre = i;
			}
		}

		for (int i = 0; i < s.length(); i++) {
			max = Math.max(max, len[i]);
			// System.out.println(sets[i] == null ? "null" : sets[i].size() +
			// ":" + len[i]);
		}

		return max;
	}