Posts published in “String”

花花酱 LeetCode 1432. Max Difference You Can Get From Changing an Integer

By zxi on May 3, 2020

You are given an integer num. You will apply the following steps exactly two times:

Pick a digit x (0 <= x <= 9).
Pick another digit y (0 <= y <= 9). The digit y can be equal to x.
Replace all the occurrences of x in the decimal representation of num by y.
The new integer cannot have any leading zeros, also the new integer cannot be 0.

Let a and b be the results of applying the operations to num the first and second times, respectively.

Return the max difference between a and b.

Example 1:

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.
The second time pick x = 5 and y = 1 and store the new integer in b.
We have now a = 999 and b = 111 and max difference = 888

Example 2:

Input: num = 9
Output: 8
Explanation: The first time pick x = 9 and y = 9 and store the new integer in a.
The second time pick x = 9 and y = 1 and store the new integer in b.
We have now a = 9 and b = 1 and max difference = 8

Example 3:

Input: num = 123456
Output: 820000

Example 4:

Input: num = 10000
Output: 80000

Example 5:

Input: num = 9288
Output: 8700

Constraints:

1 <= num <= 10^8

Solution 1: Brute Force

Try all possible pairs of (x, y)

Time complexity: O(10*10*logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int maxDiff(int num) {

int min_num = INT_MAX;

int max_num = INT_MIN;

for (char x = '0'; x <= '9'; ++x)

for (char y = '0'; y <= '9'; ++y) {

string n = to_string(num);

for (char& c : n)

if (c == x) c = y;

if (n[0] == '0') continue;

int v = stoi(n);

min_num = min(min_num, v);

max_num = max(max_num, v);

}

return max_num - min_num;

}

};

Solution 2: Greedy

Maximize A and Minimize B

A – B will the answer.

To maximize A, find the left most digit that is not 9, replace that digit with 9.
e.g. 121 => 919
e.g. 9981 => 9991
To minimize B, fin the left most digit that is not 1 or 0, replace that digit with 0 (if not the first one) or 1.
e.g. 1024 -> 1004
e.g. 2024 -> 1014

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int maxDiff(int num) {

string s = to_string(num);

const int n = s.length();

string n1(s);

string n2(s);

s += '#'; // append an unmatchable char to avoid out_of_bound.

int x = 0;

int y = 0;

while (x < n && (s[x] == '0' || s[x] == '1')) ++x;

while (y < n && s[y] == '9') ++y;

for (char& c : n1)

if (c == s[x]) c = x ? '0' : '1';

for (char& c : n2)

if (c == s[y]) c = '9';

return stoi(n2) - stoi(n1);

}

};

花花酱 LeetCode 1417. Reformat The String

By zxi on April 20, 2020

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Two streams

Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.

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

C++

// Author: Huahua

class Solution {

public:

string reformat(string s) {

string q1;

string q2;

for (char c : s) {

if (isalpha(c))

q1 += c;

else

q2 += c;

}

if (q1.length() < q2.length())

swap(q1, q2);

if (q1.length() > q2.length() + 1)

return "";

string ans;

while (!q1.empty()) {

ans += q1.back();

q1.pop_back();

if (q2.empty()) break;

ans += q2.back();

q2.pop_back();

}

return ans;

}

};

花花酱 LeetCode 1408. String Matching in an Array

By zxi on April 11, 2020

Given an array of string words. Return all strings in words which is substring of another word in any order.

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] contains only lowercase English letters.
It’s guaranteed that words[i] will be unique.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<string> stringMatching(vector<string>& words) {

vector<string> ans;

const int n = words.size();

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

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

if (i == j) continue;

if (words[j].find(words[i]) != string::npos) {

ans.push_back(words[i]);

break;

}

return ans;

}

};

花花酱 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 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;

}

};