Posts tagged as “string”

花花酱 LeetCode 1405. Longest Happy String

By zxi on April 5, 2020

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

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

C++

// Author: Huahua

class Solution {

public:

string longestDiverseString(int a, int b, int c) {

const int total = a + b + c;

vector<int> f{a, b, c};

vector<int> l{0, 0, 0};

string ans;

for (int _ = 0; _ < total; ++_)

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

const int j = (i + 1) % 3;

const int k = (i + 2) % 3;

if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2)

|| (f[i] > 0 && (l[j] == 2 || l[k] == 2))) {

ans += 'a' + i;

++l[i];

--f[i];

l[j] = l[k] = 0;

break;

}

return ans;

}

};

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

By zxi on April 5, 2020

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == '1'

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int numSteps(string s) {

int ans = 0;

int carry = 0;

// The highest bit must be 1,

// process to the 2nd highest bit

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

if (s[i] - '0' + carry == 1) {

ans += 2; // odd: +1, even: / 2

carry = 1; // always has a carry

} else {

ans += 1; // even: / 2

// carray remains e.g. 1 + 1 = 10, or 0 + 0 = 00

}

// If there is a carry, then it's even, one more step.

return ans + carry;

}

};

Python3

# Author: Huahua

class Solution:

def numSteps(self, s: str) -> int:

ans, carry = 0, 0

for i in range(1, len(s)):

if ord(s[-i]) - ord('0') + carry == 1:

ans += 2

carry = 1

else:

ans += 1

return ans + carry

花花酱 LeetCode 1392. Longest Happy Prefix

By zxi on March 21, 2020

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Rolling Hash

Time complexity: O(n) / worst case: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(string_view s) {

const int kMod = 16769023;

const int kBase = 128;

const int n = s.length();

int p = 0;

int q = 0;

int a = 1;

int ans = 0;

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

p = (p + a * s[i - 1]) % kMod;

q = (q * kBase + s[n - i]) % kMod;

a = (a * kBase) % kMod;

if (p == q && s.substr(0, i) == s.substr(n - i))

ans = i;

}

return string(s.substr(0, ans));

}

};

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

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

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

for (int i = 1; i <= s.size(); ++i)

for (int j = 1; i + j <= s.size(); ++j)

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False

花花酱 LeetCode 165. Compare Version Numbers

By zxi on March 9, 2020

Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"

Note:

Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
Version strings do not start or end with dots, and they will not be two consecutive dots.

Solution: String

Split the version string to a list of numbers, and compare two lists.

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

// Author: Huahua

class Solution {

public:

int compareVersion(string version1, string version2) {

const auto& v1 = parseVersion(version1);

const auto& v2 = parseVersion(version2);

int i1 = 0, i2 = 0;

while (i1 < v1.size() || i2 < v2.size()) {

int n1 = i1 < v1.size() ? v1[i1++] : 0;

int n2 = i2 < v2.size() ? v2[i2++] : 0;

if (n1 < n2) return -1;

else if (n1 > n2) return 1;

}

return 0;

}

private:

vector<int> parseVersion(const string& version) {

vector<int> v;

int s = 0;

for (char c : version) {

if (c == '.') {

v.push_back(s);

s = 0;

} else {

s = s * 10 + (c - '0');

}

v.push_back(s);

return v;

}

};