Posts tagged as “frequency”

花花酱 LeetCode 1781. Sum of Beauty of All Substrings

By zxi on March 6, 2021

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

For example, the beauty of "abaacc" is 3 - 1 = 2.

Given a string s, return the sum of beauty of all of its substrings.

Example 1:

Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Example 2:

Input: s = "aabcbaa"
Output: 17

Constraints:

1 <= s.length <=500
s consists of only lowercase English letters.

Solution: Treemap

Time complexity: O(n²log26)
Space complexity: O(26)

C++

// Author: Huahua

class Solution {

public:

int beautySum(string_view s) {

const int n = s.size();

int ans = 0;

vector<int> f(26);

map<int, int> m;

for (int i = 0; i < n; ++i) {

fill(begin(f), end(f), 0);

m.clear();

for (int j = i; j < n; ++j) {

const int c = ++f[s[j] - 'a'];

++m[c];

if (c > 1) {

auto it = m.find(c - 1);

if (--it->second == 0)

m.erase(it);

}

ans += rbegin(m)->first - begin(m)->first;

}

return ans;

}

};

花花酱 LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique

By zxi on November 7, 2020

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

Input: s = "aab"
Output: 0
Explanation: s is already good.

Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Solution: Hashtable

The deletion order doesn’t matter, we can process from ‘a’ to ‘z’. Use a hashtable to store the “final frequency” so far, for each char, decrease its frequency until it becomes unique in the final frequency hashtable.

Time complexity: O(n + 26^2)
Space complexity: O(26)

C++

class Solution {

public:

int minDeletions(string s) {

vector<int> freq(26);

for (char c : s) ++freq[c - 'a'];

unordered_set<int> seen;

int ans = 0;

for (int f : freq) {

while (f && !seen.insert(f).second) {

--f;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

By zxi on September 5, 2020

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]² == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]² == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5

Solution: Hashtable

For each number y in the second array, count its frequency.

For each number x in the first, if x * x % y == 0, let r = x * x / y
if r == y: ans += f[y] * f[y-1]
else ans += f[y] * f[r]

Final ans /= 2

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int numTriplets(vector<int>& nums1, vector<int>& nums2) {

return solve(nums1, nums2) + solve(nums2, nums1);

}

private:

int solve(vector<int>& nums1, vector<int>& nums2) {

int ans = 0;

unordered_map<int, int> f;

for (int y : nums2) ++f[y];

for (long x : nums1)

for (const auto& [y, c] : f) {

long r = x * x / y;

if (x * x % y || !f.count(r)) continue;

if (r == y) ans += c * (c - 1);

else ans += c * f[r];

}

return ans / 2;

}

};

花花酱 LeetCode 1525. Number of Good Ways to Split a String

By zxi on July 25, 2020

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

Constraints:

s contains only lowercase English letters.
1 <= s.length <= 10^5

Solution: Sliding Window

Count the frequency of each letter and count number of unique letters for the entire string as right part.
Iterate over the string, add current letter to the left part, and remove it from the right part.
We only
1. increase the number of unique letters when its frequency becomes to 1
2. decrease the number of unique letters when its frequency becomes to 0

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int numSplits(string s) {

vector<int> r(26);

vector<int> l(26);

int cr = 0;

for (char c : s)

cr += (++r[c - 'a'] == 1);

int ans = 0;

int cl = 0;

for (char c : s) {

cl += (++l[c - 'a'] == 1);

cr -= (--r[c - 'a'] == 0);

ans += cl == cr;

}

return ans;

}

};

java

class Solution {

public int numSplits(String s) {

int[] l = new int[26];

int[] r = new int[26];

int ans = 0;

int cl = 0;

int cr = 0;

for (char c : s.toCharArray())

if (++r[c - 'a'] == 1) ++cr;

for (char c : s.toCharArray()) {

if (++l[c - 'a'] == 1) ++cl;

if (--r[c - 'a'] == 0) --cr;

if (cl == cr) ++ans;

}

return ans;

}

Python3

class Solution:

def numSplits(self, s: str) -> int:

s = [ord(c) - ord('a') for c in s]

l, r = [0] * 26, [0] * 26

cl, cr, ans = 0, 0, 0

for c in s:

r[c] += 1

if r[c] == 1: cr += 1

for c in s:

l[c] += 1

r[c] -= 1

if l[c] == 1: cl += 1

if r[c] == 0: cr -= 1

if cl == cr: ans += 1

return ans

花花酱 LeetCode 1497. Check If Array Pairs Are Divisible by k

By zxi on June 28, 2020

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Example 4:

Input: arr = [-10,10], k = 2
Output: true

Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

Solution: Mod and Count

Count the frequency of (x % k + k) % k.
f[0] should be even (zero is also even)
f[1] = f[k -1] ((1 + k – 1) % k == 0)
f[2] = f[k -2] ((2 + k – 2) % k == 0)
…
Time complexity: O(n)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

bool canArrange(vector<int>& arr, int k) {

vector<int> f(k);

for (int x : arr) ++f[(x % k + k) % k];

for (int i = 1; i < k; ++i)

if (f[i] != f[k - i]) return false;

return f[0] % 2 == 0;

}

};