Posts tagged as “easy”

花花酱 LeetCode 2042. Check if Numbers Are Ascending in a Sentence

By zxi on October 17, 2021

A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.

Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).

Return true if so, or false otherwise.

Example 1:

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

Example 2:

Input: s = "hello world 5 x 5"
Output: false
Explanation: The numbers in s are: 5, 5. They are not strictly increasing.

Example 3:

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.

Example 4:

Input: s = "4 5 11 26"
Output: true
Explanation: The numbers in s are: 4, 5, 11, 26.
They are strictly increasing from left to right: 4 < 5 < 11 < 26.

Constraints:

3 <= s.length <= 200
s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
The number of tokens in s is between 2 and 100, inclusive.
The tokens in s are separated by a single space.
There are at least two numbers in s.
Each number in s is a positive number less than 100, with no leading zeros.
s contains no leading or trailing spaces.

Solution: String

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

C++

// Author: Huahua

class Solution {

public:

bool areNumbersAscending(string s) {

stringstream ss(s);

string token;

int last = -1;

while (ss >> token) {

if (isdigit(token[0])) {

int num = stoi(token);

if (num <= last) return false;

last = num;

}

return true;

}

};

花花酱 LeetCode 2027. Minimum Moves to Convert String

By zxi on October 4, 2021

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return the minimum number of moves required so that all the characters of s are converted to 'O'.

Example 1:

Input: s = "XXX"
Output: 1
Explanation: XXX -> OOO
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints:

3 <= s.length <= 1000
s[i] is either 'X' or 'O'.

Solution: Straight Forward

if s[i] == ‘X’, change s[i], s[i + 1] and s[i + 2] to ‘O’.

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

C++

class Solution {

public:

int minimumMoves(string s) {

const int n = s.length();

int ans = 0;

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

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

ans += 1;

i += 2;

}

return ans;

}

};

花花酱 LeetCode 1903. Largest Odd Number in String

By zxi on August 15, 2021

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

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

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints:

1 <= num.length <= 10⁵
num only consists of digits and does not contain any leading zeros.

Solution: Find right most odd digit

We just need to find the right most digit that is odd, answer will be num[0:r].

Answer must start with num[0].
Proof:
Assume the largest number is num[i:r] i > 0, we can always extend to the left, e.g. num[i-1:r] which is also an odd number and it’s larger than num[i:r] which contradicts our assumption. Thus the largest odd number (if exists) must start with num[0].

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

C++

// Author: Huahua

class Solution {

public:

string largestOddNumber(string num) {

for (int i = num.length() - 1; i >= 0; --i)

if ((num[i] - '0') & 1) return num.substr(0, i + 1);

return "";

}

};

花花酱 LeetCode 1897. Redistribute Characters to Make All Strings Equal

By zxi on August 11, 2021

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

Example 1:

Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Move the first 'a' in words[1] to the front of words[2],
to make words[1] = "abc" and words[2] = "abc".
All the strings are now equal to "abc", so return true.

Example 2:

Input: words = ["ab","a"]
Output: false
Explanation: It is impossible to make all the strings equal using the operation.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Solution: Hashtable

Count the frequency of each character, it must be a multiplier of n such that we can evenly distribute it to all the words.
e.g. n = 3, a = 9, b = 6, c = 3, each word will be “aaabbc”.

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

C++

// Author: Huahua

class Solution {

public:

bool makeEqual(vector<string>& words) {

vector<int> freq(26);

for (const auto& word : words)

for (char c : word)

++freq[c - 'a'];

for (int f : freq)

if (f % words.size()) return false;

return true;

}

};

Python3 one-liner

# Author: Huahua

class Solution:

def makeEqual(self, words: List[str]) -> bool:

return all(c % len(words) == 0 for c in Counter(''.join(words)).values())

花花酱 LeetCode 1893. Check if All the Integers in a Range Are Covered

By zxi on August 9, 2021

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [start_i, end_i] represents an inclusive interval between start_i and end_i.

Return true if each integer in the inclusive range [left, right] is covered by at least one interval in ranges. Return false otherwise.

An integer x is covered by an interval ranges[i] = [start_i, end_i] if start_i <= x <= end_i.

Example 1:

Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.

Example 2:

Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.

Constraints:

1 <= ranges.length <= 50
1 <= start_i <= end_i <= 50
1 <= left <= right <= 50

Solution 1: Hashtable

Time complexity: O(n * (right – left))
Space complexity: O(right – left)

C++

// Author: Huahua

class Solution {

public:

bool isCovered(vector<vector<int>>& ranges, int left, int right) {

unordered_set<int> s;

for (const auto& range : ranges)

for (int i = max(left, range[0]); i <= min(right, range[1]); ++i)

s.insert(i);

return s.size() == right - left + 1;

}

};