Leetcode: Longest Substring with At Most Two Distinct Characters
LeetCode with at two substring Longest Distinct characters
2023-09-11 14:14:08 时间
Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example, Given s = “eceba”, T is "ece" which its length is 3.
方法一:用HashMap, map里面存元素及其出现次数。维护一个最大长度。用两个指针,右指针一直走到出现3个dinstinct character为止。然后调整左指针删元素,直接从左往右逐个字符的删除,一直删到某个字符不会再出现。判断字符被删光就看次数是否减为了0.
采用方法:
1 public class Solution { 2 public int lengthOfLongestSubstringTwoDistinct(String s) { 3 if (s==null || s.length()==0) return 0; 4 HashMap<Character, Integer> map = new HashMap<Character, Integer>(); 5 int longest = 0; 6 int l = 0; 7 int r = 0; 8 while (r < s.length()) { 9 // move right edge 10 char c = s.charAt(r); 11 map.put(c, map.getOrDefault(c, 0) + 1); 12 13 // move left edge when necessary to make window valid again 14 while (map.size() >= 3 && l <= r) { 15 char d = s.charAt(l); 16 if (map.get(d) > 1) map.put(d, map.get(d)-1); 17 else map.remove(d); 18 l++; 19 } 20 21 // calculate the longest window 22 longest = Math.max(longest, r - l + 1); 23 r ++; 24 } 25 return longest; 26 } 27 }
这里每个元素都会进入窗口一次,最多出窗口一次,所以平摊在每个元素上的时间复杂度是O(1),总时间复杂度为O(N)
Method 2: window never shrink, can possibly be faster
相关文章
- Leetcode: Word Squares && Summary: Another Important Implementation of Trie(Retrieve all the words with a given Prefix)
- Leetcode: Longest Substring with At Least K Repeating Characters
- leetcode笔记:Merge Sorted Array
- 【Leetcode】2104. 子数组范围和(中等)
- [LeetCode] Substring with Concatenation of All Words
- 基于人脸识别的考勤系统 — Flask App — With GUI — with source code
- [LeetCode]11. 盛最多水的容器
- 【LeetCode】25. Reverse Nodes in k-Group (2 solutions)
- 【LeetCode】138. Copy List with Random Pointer
- 【LeetCode】27. Remove Element (2 solutions)
- [LeetCode OJ] Copy List with Random Pointer 扩大
- [LeetCode] 1276. Number of Burgers with No Waste of Ingredients 不浪费原料的汉堡制作方案
- [LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters 串联字符串的最大长度
- [LeetCode] 1016. Binary String With Substrings Representing 1 To N 子串能表示从1到N数字的二进制串
- [LeetCode] 1010. Pairs of Songs With Total Durations Divisible by 60 总持续时间可被60整除的歌曲
- [LeetCode] 947. Most Stones Removed with Same Row or Column 移除最多的同行或同列石头
- [LeetCode] 923. 3Sum With Multiplicity 三数之和的多种情况
- [LeetCode] 805. Split Array With Same Average 分割数组成相同平均值的小数组
- [LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串
- [LeetCode] Single Number 单独的数字