Problems Solved:
- #1004 Max Consecutive Ones III
- #438 Find All Anagrams in a String
This continues my daily series (Day 19: Sliding Window β Max Ones + Anagram Indices). Today I worked on two core sliding window problems: maximizing consecutive 1s with up to k
flips, and finding all starting indices of anagram substrings.
π‘ What I Learned
- For Max Consecutive Ones III, the sliding window expands with the right pointer and contracts when more than
k
zeros are in the window. This ensures the longest valid window is always tracked. - For Find All Anagrams in a String, maintaining a frequency counter for both the target string
p
and the current window ofs
allows us to detect valid anagrams inO(n)
. - Both problems reinforce the sliding window template: grow the window, shrink when invalid, and update results.
π§© #1004 β Max Consecutive Ones III
Python
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n, right = len(nums), 0
left = 0
temp_k = k
max_temp = 0
while right < n:
if nums[right] == 0:
temp_k -= 1
while temp_k < 0:
if nums[left] == 0:
temp_k += 1
left += 1
max_temp = max(max_temp, right - left + 1)
right += 1
return max_temp
C++
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int left = 0, right = 0;
int temp_k = k;
int max_temp = 0;
while (right < n) {
if (nums[right] == 0) {
temp_k--;
}
while (temp_k < 0) {
if (nums[left] == 0) {
temp_k++;
}
left++;
}
max_temp = max(max_temp, right - left + 1);
right++;
}
return max_temp;
}
};
Time: O(n)
Space: O(1)
π§© #438 β Find All Anagrams in a String
Python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, right = len(s), len(p)
if right > n:
return []
need = Counter(p)
window = Counter(s[:right])
start_index = []
if need == window:
start_index.append(0)
for i in range(right, n):
window[s[i]] += 1
left_c = s[i - right]
window[left_c] -= 1
if window[left_c] == 0:
del window[left_c]
if window == need:
start_index.append(i - right + 1)
return start_index
C++
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size();
int m = p.size();
if (m > n) return {};
vector<int> need(26, 0), window(26, 0);
for (char c : p) need[c - 'a']++;
vector<int> res;
int left = 0, right = 0;
while (right < n) {
window[s[right] - 'a']++;
right++;
if (right - left == m) {
if (window == need) res.push_back(left);
window[s[left] - 'a']--;
left++;
}
}
return res;
}
};
Time: O(n)
Space: O(26)
β O(1)
πΈ Achievements
- Implemented sliding window expansion/shrink for max ones with flips.
- Found all anagram indices using frequency matching in Python and C++.
π¦ Complexity Recap
-
Max Consecutive Ones III:
O(n)
time,O(1)
space. -
Find All Anagrams in a String:
O(n)
time,O(1)
space.
π£ Join the Journey
Iβm solving and documenting problems daily in both Python and C++, covering arrays, sliding window, linked lists, and trees. Follow along if youβre interested in systematic problem solving.
Links
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)