Posts tagged as “prefix”

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Solution1: Prefix Sum + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

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

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

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

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};

花花酱 LeetCode 1638. Count Substrings That Differ by One Character

By zxi on October 31, 2020

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.

Return the number of substrings that satisfy the condition above.

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

Example 1:

Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.

Example 2:

Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.

Example 3:

Input: s = "a", t = "a"
Output: 0

Example 4:

Input: s = "abe", t = "bbc"
Output: 10

Constraints:

1 <= s.length, t.length <= 100
s and t consist of lowercase English letters only.

Solution1: All Pairs + Prefix Matching

match s[i:i+p] with t[j:j+p], is there is one missed char, increase the ans, until there are two miss matched chars or reach the end.

Time complexity: O(m*n*min(m,n))
Space complexity: O(1)

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0, diff = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j, diff = 0)

for (int p = 0; i + p < m && j + p < n && diff <= 1; ++p)

if ((diff += (s[i + p] != t[j + p])) == 1) ++ans;

return ans;

}

};

Solution 2: Continuous Matching

Start matching s[0] with t[j] and s[i] with t[0]

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

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0;

auto helper = [&](int i, int j) {

for (int cur = 0, pre = 0; i < m && j < n; ++i, ++j) {

++cur;

if (s[i] != t[j]) {

pre = cur;

cur = 0;

}

ans += pre;

}

};

for (int i = 0; i < m; ++i) helper(i, 0);

for (int j = 1; j < n; ++j) helper(0, j);

return ans;

}

};

花花酱 LeetCode 1542. Find Longest Awesome Substring

By zxi on August 10, 2020

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

Time complexity: O(n)
Space complexity: O(2^10) = O(1)

C++

class Solution {

public:

int longestAwesome(string s) {

constexpr int kInf = 1e9;

vector<int> idx(1024, kInf);

idx[0] = -1;

int mask = 0; // prefix's state 0:even, 1:odd

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

mask ^= (1 << (s[i] - '0'));

ans = max(ans, i - idx[mask]);

// One digit with odd count is allowed.

for (int j = 0; j < 10; ++j)

ans = max(ans, i - idx[mask ^ (1 << j)]);

idx[mask] = min(idx[mask], i);

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int longestAwesome(String s) {

final int n = s.length();

int[] idx = new int[1024];

Arrays.fill(idx, n);

idx[0] = -1;

int mask = 0;

int ans = 0;

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

mask ^= (1 << (s.charAt(i) - '0'));

ans = Math.max(ans, i - idx[mask]);

for (int j = 0; j < 10; ++j)

ans = Math.max(ans,

i - idx[mask ^ (1 << j)]);

idx[mask] = Math.min(idx[mask], i);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

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

idx = [-1] + [len(s)] * 1023

ans, mask = 0, 0

for i, c in enumerate(s):

mask ^= 1 << (ord(c) - ord('0'))

ans = max([ans, i - idx[mask]]

+ [i - idx[mask ^ (1 << j)] for j in range(10)])

idx[mask] = min(idx[mask], i)

return ans

花花酱 LeetCode 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

By zxi on May 23, 2020

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

Constraints:

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Solution 1: Brute Force

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

C++

class Solution {

public:

int isPrefixOfWord(string sentence, string searchWord) {

const int n = sentence.size();

const int l = searchWord.size();

int word = 0;

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

if (i == 0 || sentence[i - 1] == ' ') {

++word;

bool valid = true;

for (int j = 0; j < l && valid; ++j)

valid = valid && (sentence[i + j] == searchWord[j]);

if (valid) return word;

}

return -1;

}

};

花花酱 LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

By zxi on May 11, 2020

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Solution 1: Brute Force (TLE)

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

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

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

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

int a = 0;

int b = 0;

for (int t = i; t < j; ++t)

a ^= arr[t];

for (int t = j; t <= k; ++t)

b ^= arr[t];

if (a == b) ++ans;

}

return ans;

}

};

Solution 2: Prefix XORs

Let xors[i] = arr[0] ^ arr[1] ^ … ^ arr[i-1]
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = (arr[0] ^ … ^ arr[j – 1]) ^ (arr[0] ^ … ^ arr[i-1]) = xors[j] ^ xors[i]

We then can compute a and b in O(1) time.

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

C++

// Author: Huahua, 232 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

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

const int a = xors[j] ^ xors[i];

const int b = xors[k + 1] ^ xors[j];

if (a == b) ++ans;

}

return ans;

}

};

Solution 3: Prefix XORs II

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
a == b => a ^ b == 0
XORs(i ~ k) == 0
XORS(0 ~ k) ^ XORs(0 ~ i – 1) = 0

Problem => find all pairs of (i – 1, k) such that xors[k+1] == xors[i]
For each pair (i – 1, k), there are k – i positions we can insert j.

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

if (xors[k + 1] == xors[i])

ans += k - i;

return ans;

}

};

Solution 3: HashTable

Similar to target sum, use a hashtable to store the frequency of each prefix xors.

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

C++

// Author: Huahua

// Author: Huahua 4 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

unordered_map<int, int> freq{{0, 1}};

unordered_map<int, int> sum;

int X = 0;

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

X ^= arr[i];

ans += freq[X] * i - sum[X];

++freq[X];

sum[X] += i + 1;

}

return ans;

}

};