713. Subarray Product Less Than K
Given an integer array nums and an integer k, return the number of continuous subarrays where the product of all elements is strictly less than k.
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays with product less than 100 are: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]. Note that [10,5,2] is not a valid subarray.
Sliding Window Solution
int numSubarrayProductLessThanK(int* nums, int numsSize, int k) {
int result = 0;
int left = 0;
long long product = 1;
for (int right = 0; right < numsSize; right++) {
product *= nums[right];
while (left <= right && product >= k) {
product /= nums[left];
left++;
}
result += right - left + 1;
}
return result;
}
643. Maximum Average Subarray I
Given an integer array nums of length n and an integer k, find the contiguous subarray of length k that has the maximum average value.
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
double findMaxAverage(int* nums, int numsSize, int k) {
int maxSum = INT_MIN;
int left = 0;
int currentSum = 0;
for (int right = 0; right < numsSize; right++) {
currentSum += nums[right];
if (right - left + 1 > k) {
currentSum -= nums[left];
left++;
}
if (right - left + 1 == k) {
maxSum = fmax(maxSum, currentSum);
}
}
return (double)maxSum / k;
}
3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc", length 3.
Sliding Window with Hash Table
int lengthOfLongestSubstring(char* s) {
int result = 0;
int freq[128] = {0};
int left = 0, right = 0, currentLen = 0;
int len = strlen(s);
while (right < len) {
if (freq[(unsigned char)s[right]] == 0) {
freq[(unsigned char)s[right]]++;
currentLen++;
right++;
} else {
freq[(unsigned char)s[left]]--;
currentLen--;
left++;
}
result = fmax(result, currentLen);
}
return result;
}
209. Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target.
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimum length satisfying the condition.
int minSubArrayLen(int target, int* nums, int numsSize) {
int result = INT_MAX;
int left = 0;
int sum = 0;
for (int right = 0; right < numsSize; right++) {
sum += nums[right];
while (sum >= target) {
result = fmin(result, right - left + 1);
sum -= nums[left];
left++;
}
}
return result == INT_MAX ? 0 : result;
}
567. Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring.
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains the permutation "ba" of s1.
Maintain a sliding window of size n and use hash tables to track character frequencies.
bool arraysEqual(int* a, int* b) {
for (int i = 0; i < 26; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
bool checkInclusion(char* s1, char* s2) {
int n = strlen(s1), m = strlen(s2);
if (n > m) return false;
int freq1[26] = {0}, freq2[26] = {0};
for (int i = 0; i < n; i++) {
freq1[s1[i] - 'a']++;
freq2[s2[i] - 'a']++;
}
if (arraysEqual(freq1, freq2)) return true;
for (int i = n; i < m; i++) {
freq2[s2[i] - 'a']++;
freq2[s2[i - n] - 'a']--;
if (arraysEqual(freq1, freq2)) return true;
}
return false;
}
594. Longest Harmonious Subsequence
A harmonious array is one where the difference between the maximum and minimum elements is exactly 1. Find the length of the longest harmonious subsequence.
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Although we need subsequence length, comparing only max and min values with difference 1 is required. Sort the array first and scan sequentially.
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int findLHS(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int result = 0;
int left = 0;
for (int right = 0; right < numsSize; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}
if (nums[right] - nums[left] == 1) {
result = fmax(result, right - left + 1);
}
}
return result;
}
1512. Number of Good Pairs
Given an array nums, count the number of good pairs where nums[i] == nums[j] and i < j.
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: Good pairs are (0,3), (0,4), (3,4), (2,5).
For each element, if n identical elements have appeared before, this element forms n good pairs as the second index.
int numIdenticalPairs(int* nums, int numsSize) {
int hash[101] = {0};
int result = 0;
for (int i = 0; i < numsSize; i++) {
result += hash[nums[i]];
hash[nums[i]]++;
}
return result;
}
2006. Count Number of Pairs with Absolute Difference K
Given an array nums and an integer k, count pairs (i, j) where i < j and |nums[i] - nums[j]| == k.
Input: nums = [1,2,2,1], k = 1
Output: 4
For each element at index j, find elements before it where nums[i] = nums[j] - k or nums[i] = nums[j] + k.
int countKDifference(int* nums, int numsSize, int k) {
int result = 0;
int hash[101] = {0};
for (int i = 0; i < numsSize; i++) {
int target1 = nums[i] - k;
if (target1 >= 0 && target1 < 101) {
result += hash[target1];
}
int target2 = nums[i] + k;
if (target2 >= 0 && target2 < 101) {
result += hash[target2];
}
hash[nums[i]]++;
}
return result;
}
930. Binary Subarrays With Sum
Given a binary array nums and an integer goal, count the number of non-empty subarrays with sum equal to goal.
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Convert the array to prefix sums. For subarray nums[i..j] to have sum goal, we need prefix[j] - prefix[i-1] = goal, which means prefix[j] = prefix[i-1] + goal.
int numSubarraysWithSum(int* nums, int numsSize, int goal) {
for (int i = 1; i < numsSize; i++) {
nums[i] += nums[i - 1];
}
int hash[30001] = {0};
int count = 0;
for (int i = 0; i < numsSize; i++) {
int target = nums[i] - goal;
if (target >= 0) {
count += hash[target];
}
hash[nums[i]]++;
}
count += hash[goal];
return count;
}
1004. Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1s if we can flip at most k zeros.
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
int longestOnes(int* nums, int numsSize, int k) {
int result = 0;
int left = 0;
int zeroCount = 0;
for (int right = 0; right < numsSize; right++) {
if (nums[right] == 0) {
zeroCount++;
}
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
result = fmax(result, right - left + 1);
}
return result;
}
1031. Maximum Sum of Two Non-Overlapping Subarrays
Given an array nums and two integers firstLen and secondLen, find the maximum sum of two non-overlapping subarrays where the first subarray has length firstLen and the second has length secondLen.
Prefix Sum Approach
The prefix sum array uses index 1 as the starting point, with presum[0] as a placeholder.
For two subarrays at positions i and j, their sums are presum[i+firstLen]-presum[i] and presum[j+secondLen]-presum[j]. Position j needs to be handled in two segments.
int maxSumTwoNoOverlap(int* nums, int numsSize, int firstLen, int secondLen) {
int presum[numsSize + 1];
int maxResult = 0;
presum[0] = 0;
for (int i = 1; i <= numsSize; i++) {
presum[i] = presum[i - 1] + nums[i - 1];
}
for (int i = 0; i <= numsSize - firstLen; i++) {
for (int j = 0; j <= i - secondLen; j++) {
int current = presum[i + firstLen] - presum[i] +
presum[j + secondLen] - presum[j];
maxResult = fmax(maxResult, current);
}
for (int j = i + firstLen; j <= numsSize - secondLen; j++) {
int current = presum[i + firstLen] - presum[i] +
presum[j + secondLen] - presum[j];
maxResult = fmax(maxResult, current);
}
}
return maxResult;
}
1156. Swap For Longest Repeating Character Substring
A string where all characters are the same is called a single-character repeating string. Given a string text, you can swap at most two characters once (or do nothing), return the longest possible single-character repeating substring.
Input: text = "ababa"
Output: 3
int maxRepOpt1(char* text) {
int n = strlen(text);
int left = 0, right = 0;
int result = 0;
int totalCount[26] = {0};
for (int i = 0; i < n; i++) {
totalCount[text[i] - 'a']++;
}
while (right < n) {
while (right < n && text[right] == text[left]) {
right++;
}
int nextLeft = right;
right++;
while (right < n && text[right] == text[left]) {
right++;
}
int maxLen = fmin(right - left, totalCount[text[left] - 'a']);
result = fmax(result, maxLen);
right = nextLeft;
left = nextLeft;
}
return result;
}
1759. Count Number of Homogenous Substrings
Given a string s, return the number of homogenous substrings. Since the answer may be large, return it modulo 10^9 + 7. A homogenous string has all identical characters.
Input: s = "abbcccaa"
Output: 13
Explanation: a(3) + aa(1) + b(2) + bb(1) + c(3) + cc(2) + ccc(1) = 13
For consecutive identical characters of length len, the number of substrings contributed is len + (len-1) + ... + 1 = len * (len + 1) / 2.
int countHomogenous(char* s) {
int n = strlen(s);
int result = 1;
int currentRun = 1;
for (int i = 1; i < n; i++) {
if (s[i] == s[i - 1]) {
currentRun++;
} else {
currentRun = 1;
}
result = (result + currentRun) % 1000000007;
}
return result;
}
Standard Sliding Window Approach
int countHomogenous(char* s) {
int n = strlen(s);
int result = 0;
int left = 0, right = 0;
while (right < n) {
if (s[left] != s[right]) {
left = right;
} else {
result = (result + right - left + 1) % 1000000007;
right++;
}
}
return result;
}
1839. Longest Substring of All Vowels in Order
A string is beautiful if all five vowels appear at least once and they appear in alphabetical order. Given a string word consisting only of vowels, return the length of the longest beautiful substring.
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: Longest beautiful substring is "aaaaeiiiiouuu" with length 13.
Use a counter to track the number of distinct vowel types in the window.
int longestBeautifulSubstring(char* word) {
int n = strlen(word);
if (n < 5) return 0;
int result = 0, vowelTypes = 1;
int left = 0;
for (int right = 1; right < n; right++) {
if (word[right - 1] > word[right]) {
left = right;
vowelTypes = 1;
}
if (word[right - 1] < word[right]) {
vowelTypes++;
}
if (vowelTypes == 5) {
result = fmax(result, right - left + 1);
}
}
return result;
}
763. Partition Labels
Divide string s into as many parts as possible such that each letter appears in at most one part. Return an array containing the length of each part.
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: Partition result: "ababcbaca", "defegde", "hijhklij".
int* partitionLabels(char* s, int* returnSize) {
int lastPos[26] = {0};
int n = strlen(s);
for (int i = 0; i < n; i++) {
lastPos[s[i] - 'a'] = i;
}
int* result = malloc(sizeof(int) * n);
int left = 0, right = 0;
int index = 0;
for (int i = 0; i < n; i++) {
right = fmax(right, lastPos[s[i] - 'a']);
if (i == right) {
result[index++] = right - left + 1;
left = right + 1;
}
}
*returnSize = index;
return result;
}