MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 826 Reading time ≈ 1 mins.

Question

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

https://leetcode.com/problems/longest-repeating-character-replacement/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0, maxCount = 0, maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 692 Reading time ≈ 1 mins.

Question

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-char

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, res = 0;
        for (int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
            while (map.size() > k){
                char c = s.charAt(left);
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) map.remove(c);
                left++;
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 728 Reading time ≈ 1 mins.

Question

Given a string s, return the length of the longest substring that contains at most two distinct characters.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, res = 0;
        for (int i = 0; i < s.length(); i++){
            //renew current character
            char cur = s.charAt(i);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
            //加条件，不符合的从left移除
            while (map.size() > 2){
                char c = s.charAt(left);
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) map.remove(c);
                left++;
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 652 Reading time ≈ 1 mins.

Question

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

https://leetcode.com/problems/minimum-size-subarray-sum/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, n = nums.length, res = Integer.MAX_VALUE, sum = 0;
        for (int i = 0; i < n; i++){
            sum += nums[i];
            while (sum >= target){
                res = Math.min(res, i - left + 1);
                sum -= nums[left++];
            }
            
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 785 Reading time ≈ 1 mins.

Question

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

https://leetcode.com/problems/range-addition/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res = new int[length];
        for (int[] update : updates){
            int value = update[2];
            int start = update[0];
            int end = update[1];
            res[start] += value;
            if (end < length - 1) res[end + 1] -= value;
        }
        int sum = 0;
        for (int i = 0; i < length; i++){
            sum += res[i];
            res[i] = sum;
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 573 Reading time ≈ 1 mins.

Question

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

https://leetcode.com/problems/contiguous-array/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMaxLength(int[] nums) {
        for (int i = 0; i < nums.length; i++) if (nums[i] == 0) nums[i] = -1;
        int res = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            if (map.containsKey(sum)) res = Math.max(res, i - map.get(sum));
            else map.put(sum, i);
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 695 Reading time ≈ 1 mins.

Question

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

https://leetcode.com/problems/continuous-subarray-sum/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            if (k != 0) sum %= k;
            if (map.containsKey(sum)){
                if (i - map.get(sum) > 1) return true;
            } else map.put(sum, i);
        }
        return false;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 612 Reading time ≈ 1 mins.

Question

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

https://leetcode.com/problems/subarray-sums-divisible-by-k/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0, sum = 0;
        for(int a : A) {
            sum = (sum + a) % K;
            if(sum < 0) sum += K;  // Because -1 % 5 = -1, but we need the positive mod 4
            count += map.getOrDefault(sum, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

https://leetcode.com/problems/minimum-window-substring/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c] += 1;
        }
        int begin = 0;
        int len = Integer.MAX_VALUE;
        int count = t.length();
        for (int left=0, right=0; right<s.length(); right++) {
            char c = s.charAt(right);
            map[c]--;
            if(map[c]>=0) count--;
            //count = 0, 第一个适配的找到啦
            //缩减范围
            while (count == 0) {
                char lc = s.charAt(left);
                map[lc]++;
                //目标种的一个出了窗口
                if (map[lc]>0) {
                    if (right-left+1<len) {
                        begin = left;
                        len = right-left+1;
                    }
                    count++;
                }
                left++;
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(begin, begin+len);
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 539 Reading time ≈ 1 mins.

Question

Given a string s, find the length of the longest substring without repeating characters.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, res = 0;
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            //左指针将重复元素移除
            while (!set.add(c)) set.remove(s.charAt(left++));
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)