Posts tagged as “string”

花花酱 LeetCode 2586. Count the Number of Vowel Strings in Range

By zxi on March 11, 2023

You are given a 0-indexed array of string words and two integers left and right.

A string is called a vowel string if it starts with a vowel character and ends with a vowel character where vowel characters are 'a', 'e', 'i', 'o', and 'u'.

Return the number of vowel strings words[i] where i belongs to the inclusive range [left, right].

Example 1:

Input: words = ["are","amy","u"], left = 0, right = 2
Output: 2
Explanation: 
- "are" is a vowel string because it starts with 'a' and ends with 'e'.
- "amy" is not a vowel string because it does not end with a vowel.
- "u" is a vowel string because it starts with 'u' and ends with 'u'.
The number of vowel strings in the mentioned range is 2.

Example 2:

Input: words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
Output: 3
Explanation: 
- "aeo" is a vowel string because it starts with 'a' and ends with 'o'.
- "mu" is not a vowel string because it does not start with a vowel.
- "ooo" is a vowel string because it starts with 'o' and ends with 'o'.
- "artro" is a vowel string because it starts with 'a' and ends with 'o'.
The number of vowel strings in the mentioned range is 3.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 10
words[i] consists of only lowercase English letters.
0 <= left <= right < words.length

Solution:

Iterator overs words, from left to right. Check the first and last element of the string.

Time complexity: O(|right – left + 1|)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int vowelStrings(vector<string>& words, int left, int right) {

auto isVowel = [](char c) {

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

};

return count_if(begin(words) + left, begin(words) + right + 1, [&](const string& w) {

return isVowel(w.front()) && isVowel(w.back());

});

}

};

花花酱 LeetCode 2564. Substring XOR Queries

By zxi on February 12, 2023

You are given a binary string s, and a 2D integer array queries where queries[i] = [first_i, second_i].

For the i^th query, find the shortest substring of s whose decimal value, val, yields second_i when bitwise XORed with first_i. In other words, val ^ first_i == second_i.

The answer to the i^th query is the endpoints (0-indexed) of the substring [left_i, right_i] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum left_i.

Return an array ans where ans[i] = [left_i, right_i] is the answer to the i^th query.

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

Example 1:

Input: s = "101101", queries = [[0,5],[1,2]]
Output: [[0,2],[2,3]]
Explanation: For the first query the substring in range [0,2] is "101" which has a decimal value of 5, and 5 ^ 0 = 5, hence the answer to the first query is [0,2]. In the second query, the substring in range [2,3] is "11", and has a decimal value of 3, and 3 ^ 1 = 2. So, [2,3] is returned for the second query.

Example 2:

Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.

Example 3:

Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Explanation: For this example, the substring in range [0,0] has a decimal value of 1, and 1 ^ 4 = 5. So, the answer is [0,0].

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.
1 <= queries.length <= 10⁵
0 <= first_i, second_i <= 10⁹

Solution: Pre-compute

We can pre-compute all possible substrings

Time complexity: O(n*32 + m)
Space complexity: O(n*32)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {

unordered_map<int, vector<int>> m;

const int l = s.length();

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

if (s[i] == '0') {

if (!m.count(0)) m[0] = {i, i};

continue;

}

for (int j = 0, cur = 0; j < 32 && i + j < l; ++j) {

cur = (cur << 1) | (s[i + j] - '0');

if (!m.count(cur))

m[cur] = {i, i + j};

}

vector<vector<int>> ans;

for (const auto& q : queries) {

int x = q[0] ^ q[1];

if (m.count(x))

ans.push_back(m[x]);

else

ans.push_back({-1, -1});

}

return ans;

}

};

花花酱 LeetCode 2559. Count Vowel Strings in Ranges

By zxi on February 4, 2023

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l_i, r_i] asks us to find the number of strings present in the range l_i to r_i (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the i^th query.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].

Constraints:

1 <= words.length <= 10⁵
1 <= words[i].length <= 40
words[i] consists only of lowercase English letters.
sum(words[i].length) <= 3 * 10⁵
1 <= queries.length <= 10⁵
0 <= l_i <= r_i < words.length

Solution: Prefix Sum

Let sum[i] := number of valid strings in words[0:i]

For each query [l, r], answer will be sum[r + 1] – sum[l]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {

const size_t n = words.size();

vector<int> sum(n + 1);

auto check = [](char c) {

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

};

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

sum[i + 1] = sum[i] +

(check(words[i][0]) && check(words[i][words[i].size() - 1]));

vector<int> ans;

for (const auto& q : queries)

ans.push_back(sum[q[1] + 1] - sum[q[0]]);

return ans;

}

};

花花酱 LeetCode 2452. Words Within Two Edits of Dictionary

By zxi on October 31, 2022

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints:

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
All queries[i] and dictionary[j] are composed of lowercase English letters.

Solution: Hamming distance + Brute Force

For each query word q, check the hamming distance between it and all words in the dictionary.

Time complexity: O(|q|*|d|*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {

const int n = queries[0].size();

auto check = [&](string_view q) {

for (const string& w : dictionary) {

int dist = 0;

for (int i = 0; i < n && dist <= 3; ++i)

dist += q[i] != w[i];

if (dist <= 2) return true;

}

return false;

};

vector<string> ans;

for (const string& q : queries)

if (check(q)) ans.push_back(q);

return ans;

}

};

花花酱 LeetCode 2451. Odd String Difference

By zxi on October 31, 2022

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

Constraints:

3 <= words.length <= 100
n == words[i].length
2 <= n <= 20
words[i] consists of lowercase English letters.

Solution: Comparing with first string.

Let us pick words[0] as a reference for comparison, assuming it’s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m – 1 different words which means words[0] itself is bad.

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

C++

// Author: Huahua

class Solution {

public:

string oddString(vector<string>& words) {

const int m = words.size();

const int n = words[0].size();

int count = 0;

int bad = 0;

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

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

if (words[i][j] - words[i][j - 1]

!= words[0][j] - words[0][j - 1]) {

++count;

bad = i;

break;

}

return words[count == 1 ? bad : 0];

}

};