Posts tagged as “prefix”

花花酱 LeetCode 2012. Sum of Beauty in the Array

By zxi on April 10, 2025

数据规模比较大，算法必须是O(n)的。

可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值，存在left[i]中，以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {

public:

int sumOfBeauties(vector<int>& nums) {

const int n = nums.size();

vector<int> left(n, nums[0]);

vector<int> right(n, nums.back());

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

left[i] = max(left[i - 1], nums[i]);

for (int i = n - 2; i >= 0; --i)

right[i] = min(right[i + 1], nums[i]);

int ans = 0;

for (int i = 1; i < n - 1; ++i)

if (left[i - 1] < nums[i] && nums[i] < right[i + 1])

ans += 2;

else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1])

ans += 1;

return ans;

}

};

花花酱 LeetCode 3029. Minimum Time to Revert Word to Initial State I

By zxi on February 5, 2024

You are given a 0-indexed string word and an integer k.

At every second, you must perform the following operations:

Remove the first k characters of word.
Add any k characters to the end of word.

Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.

Return the minimum time greater than zero required for word to revert to its initial state.

Example 1:

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2:

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3:

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

Constraints:

1 <= word.length <= 50
1 <= k <= word.length
word consists only of lowercase English letters.

Solution: Suffix ==? Prefix

Compare the suffix with prefix.

word = “abacaba”, k = 3
ans = 1, “~~aba~~caba” != “abac~~aba~~“
ans = 2, “~~abacab~~a” == “a~~bacaba~~“, we find it.

Time complexity: O(n * n / k)
Space complexity: O(1)

C++

class Solution {

public:

int minimumTimeToInitialState(string_view word, int k) {

const int n = word.length();

for (int i = 1; i * k < n; ++i) {

string_view t = word.substr(i * k);

if (t == word.substr(0, t.length())) return i;

}

return (n + k - 1) / k;

}

};

花花酱 LeetCode 2657. Find the Prefix Common Array of Two Arrays

By zxi on April 30, 2023

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solution 1: Bitset

Use bitsets to store the numbers seen so far for each array, and use sA & sB to count the common elements.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

bitset<51> sA;

bitset<51> sB;

vector<int> ans;

for (int i = 0; i < A.size(); ++i) {

sA.set(A[i]);

sB.set(B[i]);

ans.push_back((sA & sB).count());

}

return ans;

}

};

Solution 2: Counter

Use a counter to track the frequency of each element, when the counter[x] == 2, we found a pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

vector<int> count(A.size() + 1);

vector<int> ans;

for (int i = 0, s = 0; i < A.size(); ++i) {

if (++count[A[i]] == 2) ++s;

if (++count[B[i]] == 2) ++s;

ans.push_back(s);

}

return ans;

}

};

花花酱 LeetCode 2416. Sum of Prefix Scores of Strings

By zxi on September 18, 2022

You are given an array words of size n consisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].

For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Note that a string is considered as a prefix of itself.

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists of lowercase English letters.

Solution: Trie

Insert all the words into a tire whose node val is the number of substrings that have the current prefix.

During query time, sum up the values along the prefix path.

Time complexity: O(sum(len(word))
Space complexity: O(sum(len(word))

C++

// Author: Huahua

struct Trie {

Trie* ch[26] = {};

int cnt = 0;

void insert(string_view s) {

Trie* cur = this;

for (char c : s) {

if (!cur->ch[c - 'a'])

cur->ch[c - 'a'] = new Trie();

cur = cur->ch[c - 'a'];

++cur->cnt;

}

int query(string_view s) {

Trie* cur = this;

int ans = 0;

for (char c : s) {

cur = cur->ch[c - 'a'];

ans += cur->cnt;

}

return ans;

}

};

class Solution {

public:

vector<int> sumPrefixScores(vector<string>& words) {

Trie* root = new Trie();

for (const string& w : words)

root->insert(w);

vector<int> ans;

for (const string& w : words)

ans.push_back(root->query(w));

return ans;

}

};

花花酱 LeetCode 2256. Minimum Average Difference

By zxi on May 1, 2022

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

The absolute difference of two numbers is the absolute value of their difference.
The average of n elements is the sum of the n elements divided (integer division) by n.
The average of 0 elements is considered to be 0.

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Solution: Prefix / Suffix Sum

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

C++

// Author: Huahua

class Solution {

public:

int minimumAverageDifference(vector<int>& nums) {

const int n = nums.size();

long long suffix = accumulate(begin(nums), end(nums), 0LL);

long long prefix = 0;

int best = INT_MAX;

int ans = 0;

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

prefix += nums[i];

suffix -= nums[i];

int cur = abs(prefix / (i + 1) - (i == n - 1 ? 0 : suffix / (n - i - 1)));

if (cur < best) {

best = cur;

ans = i;

}

return ans;

}

};