Posts tagged as “string”

花花酱 LeetCode 2156. Find Substring With Given Hash Value

By zxi on February 5, 2022

The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function:

hash(s, p, m) = (val(s[0]) * p⁰ + val(s[1]) * p¹ + ... + val(s[k-1]) * p^k-1) mod m.

Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26.

You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.

The test cases will be generated such that an answer always exists.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. 
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".

Example 2:

Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31²) mod 100 = 23132 mod 100 = 32. 
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31²) mod 100 = 25732 mod 100 = 32. 
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".

Constraints:

1 <= k <= s.length <= 2 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s consists of lowercase English letters only.
The test cases are generated such that an answer always exists.

Solution: Sliding window

hash = (((hash – (s[i+k] * p^k-1) % mod + mod) * p) + (s[i] * p⁰)) % mod

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

C++

// Author: Huahua

class Solution {

public:

string subStrHash(string s, int power, int modulo, int k, int hashValue) {

const int n = s.length();

long p = 1;

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

p = (p * power) % modulo;

long ans = 0;

for (long i = n - 1, cur = 0; i >= 0; --i) {

if (i + k < n)

cur = ((cur - (s[i + k] - 'a' + 1) * p) % modulo + modulo) % modulo;

cur = (cur * power + (s[i] - 'a' + 1)) % modulo;

if (i + k <= n && cur == hashValue)

ans = i;

}

return s.substr(ans, k);

}

};

花花酱 LeetCode 2138. Divide a String Into Groups of Size k

By zxi on January 30, 2022

A string s can be partitioned into groups of size k using the following procedure:

The first group consists of the first k characters of the string, the second group consists of the next k characters of the string, and so on. Each character can be a part of exactly one group.
For the last group, if the string does not have k characters remaining, a character fill is used to complete the group.

Note that the partition is done so that after removing the fill character from the last group (if it exists) and concatenating all the groups in order, the resultant string should be s.

Given the string s, the size of each group k and the character fill, return a string array denoting the composition of every group s has been divided into, using the above procedure.

Example 1:

Input: s = "abcdefghi", k = 3, fill = "x"
Output: ["abc","def","ghi"]
Explanation:
The first 3 characters "abc" form the first group.
The next 3 characters "def" form the second group.
The last 3 characters "ghi" form the third group.
Since all groups can be completely filled by characters from the string, we do not need to use fill.
Thus, the groups formed are "abc", "def", and "ghi".

Example 2:

Input: s = "abcdefghij", k = 3, fill = "x"
Output: ["abc","def","ghi","jxx"]
Explanation:
Similar to the previous example, we are forming the first three groups "abc", "def", and "ghi".
For the last group, we can only use the character 'j' from the string. To complete this group, we add 'x' twice.
Thus, the 4 groups formed are "abc", "def", "ghi", and "jxx".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters only.
1 <= k <= 100
fill is a lowercase English letter.

Solution: Pre-fill

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

C++

// Author: Huahua

class Solution {

public:

vector<string> divideString(string s, int k, char fill) {

if (s.length() % k)

s.append(k - s.length() % k, fill);

vector<string> ans;

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

ans.push_back(s.substr(i, k));

return ans;

}

};

花花酱 LeetCode 2135. Count Words Obtained After Adding a Letter

By zxi on January 17, 2022

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

Append any lowercase letter that is not present in the string to its end.
- For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
Rearrange the letters of the new string in any arbitrary order.
- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

1 <= startWords.length, targetWords.length <= 5 * 10⁴
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Solution: Bitmask w/ Hashtable

Since there is no duplicate letters in each word, we can use a bitmask to represent a word.

Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.

E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.

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

C++

// Author: Huahua

class Solution {

public:

int wordCount(vector<string>& startWords, vector<string>& targetWords) {

unordered_set<int> s;

auto getKey = [](const string& s) {

return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); });

};

for (const string& w : startWords)

s.insert(getKey(w));

return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) {

const int key = getKey(w);

return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); });

});

}

};

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

By zxi on January 9, 2022

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

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

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

1 <= words.length <= 10⁵
words[i].length == 2
words[i] consists of lowercase English letters.

Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(vector<string>& words) {

int ans = 0;

int same = 0;

vector<vector<int>> m(26, vector<int>(26));

for (const string& word : words) {

const int a = word[0] - 'a';

const int b = word[1] - 'a';

if (m[b][a]) {

--m[b][a];

ans += 4;

} else {

++m[a][b];

}

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

if (m[i][i]) {

ans += 2;

break;

}

return ans;

}

};

花花酱 LeetCode 2129. Capitalize the Title

By zxi on January 8, 2022

You are given a string title consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

If the length of the word is 1 or 2 letters, change all letters to lowercase.
Otherwise, change the first letter to uppercase and the remaining letters to lowercase.

Return the capitalized title.

Example 1:

Input: title = "capiTalIze tHe titLe"
Output: "Capitalize The Title"
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.

Example 2:

Input: title = "First leTTeR of EACH Word"
Output: "First Letter of Each Word"
Explanation:
The word "of" has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Example 3:

Input: title = "i lOve leetcode"
Output: "i Love Leetcode"
Explanation:
The word "i" has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Constraints:

1 <= title.length <= 100
title consists of words separated by a single space without any leading or trailing spaces.
Each word consists of uppercase and lowercase English letters and is non-empty.

Solution: Straight forward

Without splitting the sentence into words, we need to take care the word of length one and two.

Tips: use std::tolower, std::toupper to transform letters.

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

C++

// Author: Huahua

class Solution {

public:

string capitalizeTitle(string title) {

const int n = title.size();

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

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

&& i + 2 < n && title[i + 1] != ' ' && title[i + 2] != ' ')

title[i] = toupper(title[i]);

else

title[i] = tolower(title[i]);

}

return title;

}

};

Python3

# Author: Huahua

class Solution:

def capitalizeTitle(self, title: str) -> str:

return " ".join(map(lambda w: w.lower() if len(w) <= 2 else w[0].upper() + w[1:].lower(), title.split()))