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.-------------------------
递归,找出当前String里数量小于k的字符的index,以这些index作为分界点,对substring进行相同操作。
O(n), n是String的长度。因为最多只有26个字符,每一层递归都会去除一个字符
class Solution { public int longestSubstring(String s, int k) { Map<Character, Integer> map = getMap(s); Stack<Integer> st = new Stack<>(); st.push(-1); for (int i = 0; i < s.length(); i++) { if (map.get(s.charAt(i)) < k) { st.push(i); } } if (st.size() == 1) return s.length(); int len = 0; int end = s.length(); while (!st.isEmpty()) { int start = st.pop(); len = Math.max(len, longestSubstring(s.substring(start + 1, end), k)); end = start; } return len; } private Map<Character, Integer> getMap(String s) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); map.put(c, map.getOrDefault(c, 0) + 1); } return map; } }
No comments:
Post a Comment