Posts tagged as “string”

花花酱 LeetCode 1773. Count Items Matching a Rule

By zxi on February 27, 2021

You are given an array items, where each items[i] = [type_i, color_i, name_i] describes the type, color, and name of the i^th item. You are also given a rule represented by two strings, ruleKey and ruleValue.

The i^th item is said to match the rule if one of the following is true:

ruleKey == "type" and ruleValue == type_i.
ruleKey == "color" and ruleValue == color_i.
ruleKey == "name" and ruleValue == name_i.

Return the number of items that match the given rule.

Example 1:

Input: items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
Output: 1
Explanation: There is only one item matching the given rule, which is ["computer","silver","lenovo"].

Example 2:

Input: items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
Output: 2
Explanation: There are only two items matching the given rule, which are ["phone","blue","pixel"] and ["phone","gold","iphone"]. Note that the item ["computer","silver","phone"] does not match.

Constraints:

1 <= items.length <= 10⁴
1 <= type_i.length, color_i.length, name_i.length, ruleValue.length <= 10
ruleKey is equal to either "type", "color", or "name".
All strings consist only of lowercase letters.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {

return count_if(begin(items), end(items), [&](const auto& item) {

return (ruleKey == "type" && item[0] == ruleValue

|| ruleKey == "color" && item[1] == ruleValue

|| ruleKey == "name" && item[2] == ruleValue);

});

}

};

花花酱 LeetCode 1771. Maximize Palindrome Length From Subsequences

By zxi on February 21, 2021

You are given two strings, word1 and word2. You want to construct a string in the following manner:

Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

Constraints:

1 <= word1.length, word2.length <= 1000
word1 and word2 consist of lowercase English letters.

Solution: DP

Let s = word1 + word2, build dp table on s. We just need to make sure there’s at least one char from each string.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

vector<vector<int>> dp(n, vector<int>(n));

for (int i = 0; i < n; ++i) dp[i][i] = 1;

for (int l = 2; l <= n; ++l)

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

if (s[i] == s[j])

dp[i][j] = dp[i + 1][j - 1] + 2;

else

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

}

int ans = 0;

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

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

if (word1[i] == word2[j])

ans = max(ans, dp[i][l1 + j]);

return ans;

}

};

O(m+n) Space complexity

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

vector<int> dp1(n, 1), dp2(n);

int ans = 0;

for (int l = 2; l <= n; ++l) {

vector<int> dp(n);

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

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

dp[i] = dp2[i + 1] + 2;

if (i < l1 && j >= l1)

ans = max(ans, dp[i]);

} else {

dp[i] = max(dp1[i + 1], dp1[i]);

}

// dp2, dp1 = dp1, dp

dp1.swap(dp);

dp2.swap(dp);

}

return ans;

}

};

花花酱 LeetCode 1764. Form Array by Concatenating Subarrays of Another Array

By zxi on February 20, 2021

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the i^th subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)^th subarray appears before the i^th subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0^th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1^st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

Constraints:

groups.length == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {

const int n = nums.size();

int s = 0;

for (const auto& g : groups) {

bool found = false;

for (int i = s; i <= n - g.size(); ++i)

if (equal(begin(g), end(g), begin(nums) + i)) {

s = i + g.size();

found = true;

break;

}

if (!found) return false;

}

return true;

}

};

花花酱 LeetCode 1763. Longest Nice Substring

By zxi on February 20, 2021

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Example 4:

Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Solution: Brute Force

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

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

auto isNice = [](string_view s) {

vector<int> u(26), l(26);

for (int c : s)

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

return u == l;

};

string_view ans;

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

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

string_view ss = s.substr(i, j - i + 1);

if (isNice(ss) && ss.length() > ans.length())

ans = ss;

}

return string(ans);

}

};

Optimized 1:

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

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

string_view ans;

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

vector<int> u(26), l(26);

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

const char c = s[j];

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

if (u == l && j - i + 1 > ans.length())

ans = s.substr(i, j - i + 1);

}

return string(ans);

}

};

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

By zxi on February 13, 2021

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10⁹ + 7.

A string is homogenous if all the characters of the string are the same.

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

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase letters.

Solution: Counting

Let m be the length of the longest homogenous substring, # of homogenous substring is m * (m + 1) / 2.
e.g. aaabb
“aaa” => m = 3, # = 3 * (3 + 1) / 2 = 6
“bb” => m = 2, # = 2 * (2+1) / 2 = 3
Total = 6 + 3 = 9

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

C++

// Author: Huahua

class Solution {

public:

int countHomogenous(string s) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

long ans = 0;

for (long i = 0, j = 0; i < n; i = j) {

while (j < n && s[i] == s[j]) ++j;

ans += (j - i) * (j - i + 1) / 2;

}

return ans % kMod;

}

};