Posts tagged as “string”

花花酱 LeetCode 2194. Cells in a Range on an Excel Sheet

By zxi on March 8, 2022

A cell (r, c) of an excel sheet is represented as a string "<col><row>" where:

<col> denotes the column number c of the cell. It is represented by alphabetical letters.
- For example, the 1^st column is denoted by 'A', the 2^nd by 'B', the 3^rd by 'C', and so on.
<row> is the row number r of the cell. The r^th row is represented by the integer r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, <col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.

Return the list of cells (x, y) such that r1 <= x <= r2 and c1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.

Example 1:

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Example 2:

Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

Constraints:

s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s consists of uppercase English letters, digits and ':'.

Solution: Brute Force

Time complexity: O((row2 – row1 + 1) * (col2 – col1 + 1))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> cellsInRange(string s) {

vector<string> ans;

for (char c = s[0]; c <= s[3]; ++c)

for (char r = s[1]; r <= s[4]; ++r)

ans.push_back(string{c, r});

return ans;

}

};

花花酱 LeetCode 2182. Construct String With Repeat Limit

By zxi on March 3, 2022

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

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

Solution: Greedy

Adding one letter at a time, find the largest one that can be used.

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

C++

// Author: Huahua

class Solution {

public:

string repeatLimitedString(string s, int repeatLimit) {

vector<int> m(26);

for (char c : s) ++m[c - 'a'];

string ans;

int count = 0;

int last = -1;

while (true) {

bool found = false;

for (int i = 25; i >= 0 && !found; --i)

if (m[i] && (count < repeatLimit || last != i)) {

ans += 'a' + i;

count = (last == i) * count + 1;

--m[i];

last = i;

found = true;

}

if (!found) break;

}

return ans;

}

};

花花酱 LeetCode 2180. Count Integers With Even Digit Sum

By zxi on February 28, 2022

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

The digit sum of a positive integer is the sum of all its digits.

Example 1:

Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.

Example 2:

Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.

Constraints:

1 <= num <= 1000

Solution: Brute Force

Use std::to_string to convert an integer to string.

Time complexity: O(nlgn)
Space complexity: O(lgn)

C++

// Author: Huahua

class Solution {

public:

int countEven(int num) {

int ans = 0;

for (int i = 1; i <= num; ++i) {

int sum = 0;

for (char c : to_string(i))

sum += (c - '0');

if (sum % 2 == 0) ++ans;

}

return ans;

}

};

花花酱 LeetCode 2186. Minimum Number of Steps to Make Two Strings Anagram II

By zxi on February 26, 2022

You are given two strings s and t. In one step, you can append any character to either s or t.

Return the minimum number of steps to make s and t anagrams of each other.

An anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "leetcode", t = "coats"
Output: 7
Explanation: 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Example 2:

Input: s = "night", t = "thing"
Output: 0
Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.

Constraints:

1 <= s.length, t.length <= 2 * 10⁵
s and t consist of lowercase English letters.

Solution: Hashtable

Record the frequency difference of each letter.

Ans = sum(diff)

Time complexity: O(m + n)
Space complexity: O(26)

C++

// Author: Huahua

class Solution {

public:

int minSteps(string s, string t) {

vector<int> diff(26);

for (char c : s) ++diff[c - 'a'];

for (char c : t) --diff[c - 'a'];

int ans = 0;

for (int d : diff)

ans += abs(d);

return ans;

}

};

花花酱 LeetCode 2185. Counting Words With a Given Prefix

By zxi on February 26, 2022

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

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

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Solution: Straight forward

We can use std::count_if and std::string::find.

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

C++

// Author: Huahua

class Solution {

public:

int prefixCount(vector<string>& words, string pref) {

return count_if(begin(words), end(words), [&](const string& w) {

return w.find(pref) == 0;

});

}

};