Huahua’s Tech Road

花花酱 LeetCode 1663. Smallest String With A Given Numeric Value

By zxi on November 22, 2020

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:

Input: n = 5, k = 73
Output: "aaszz"

Constraints:

1 <= n <= 10⁵
n <= k <= 26 * n

Solution: Greedy, Fill in reverse order

Fill the entire string with ‘a’, k-=n, then fill in reverse order, replace ‘a’ with ‘z’ until not enough k left.

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

C++

// Author: Huahua

class Solution {

public:

string getSmallestString(int n, int k) {

string ans(n, 'a');

k -= n;

while (k) {

int d = min(k, 25);

ans[--n] += d;

k -= d;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def getSmallestString(self, n: int, k: int) -> str:

ans = ['a'] * n

k -= n

i = n - 1

while k:

d = min(k, 25)

ans[i] = chr(ord(ans[i]) + d)

k -= d

i -= 1

return ''.join(ans)

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

By zxi on November 22, 2020

Given two string arrays word1 and word2, returntrue if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Solution1: Construct the string

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

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

string s1, s2;

for (const string& w1 : word1) s1 += w1;

for (const string& w2 : word2) s2 += w2;

return s1 == s2;

}

};

Solution 2: Pointers

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

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

int i1 = 0, j1 = 0;

int i2 = 0, j2 = 0;

while (i1 < word1.size() || i2 < word2.size()) {

char c1 = i1 < word1.size() ? word1[i1][j1++] : '\0';

char c2 = i2 < word2.size() ? word2[i2][j2++] : '\0';

if (c1 != c2) return false;

if (i1 < word1.size() && j1 == word1[i1].length())

++i1, j1 = 0;

if (i2 < word2.size() && j2 == word2[i2].length())

++i2, j2 = 0;

}

return true;

}

};

花花酱 Min Heap SP21

By zxi on November 18, 2020

C++

// Author: Huahua

#include <assert.h>

#include <iostream>

#include <vector>

using namespace std;

class MinHeap {

public:

// Return the min element.

int peek() const { return data_[0]; }

// Extract the min element.

int pop() {

// Swap the min element with the last one. O(1)

swap(data_.back(), data_[0]);

// Get the min element. O(1)

int min_el = data_.back();

// Evict the min element. O(1)

data_.pop_back();

// Maintain heap property. θ(logn)

heapifyDown(0);

return min_el;

}

// Add a new element to the heap.

void push(int key) {

// Add the element to the end of the array. O(1)

data_.push_back(key);

// Maintain heap property. θ(logn)

heapifyUp(data_.size() - 1);

}

// Return the size of the heap.

int size() const { return data_.size(); }

private:

void heapifyUp(int index) {

// Stop at root.

if (index == 0) return;

int parent = (index - 1) / 2;

// Stop if greater or euqal to parent.

if (data_[index] >= data_[parent]) return;

// Swap with parent.

swap(data_[index], data_[parent]);

// Continue heapifyUp on parent.

heapifyUp(parent);

}

void heapifyDown(int index) {

int left = index * 2 + 1;

int right = index * 2 + 2;

// Stop if has no left child.

if (left >= data_.size()) return;

// Get the min child.

int min_child =

right < data_.size() && data_[right] < data_[left] ? right : left;

// Stop if less or euqal to min child.

if (data_[index] <= data_[min_child])

return;

// Swap with min child.

swap(data_[index], data_[min_child]);

// Continue heapifyDown on min_child.

heapifyDown(min_child);

}

vector<int> data_;

};

int main() {

vector<int> data{5,1,3,5,3,4,3,7};

MinHeap heap;

for (int x : data)

heap.push(x);

vector<int> output;

while (heap.size())

output.push_back(heap.pop());

assert(output == vector<int>({1,3,3,3,4,5,5,7}));

}

Python3

# Author: Huahua

class MinHeap:

def __init__(self, data = None):

self.data = list(data) if data else []

for i in range((len(self.data)) // 2, -1, -1):

self.heapifyDown(i)

def push(self, key):

self.data.append(key)

self.heapifyUp(len(self.data) - 1)

def pop(self):

self.swap(0, -1)

min_el = self.data.pop()

self.heapifyDown(0)

return min_el

def size(self):

return len(self.data)

def swap(self, i, j):

self.data[i], self.data[j] = self.data[j], self.data[i]

def heapifyDown(self, i):

smallest = i

for c in [2 * i + 1, 2 * i + 2]:

if c < self.size() and self.data[c] < self.data[smallest]: smallest = c

if smallest != i:

self.swap(i, smallest)

self.heapifyDown(smallest)

def heapifyUp(self, i):

if i == 0: return

parent = (i - 1) // 2

if self.data[i] >= self.data[parent]: return

self.swap(i, parent)

self.heapifyUp(parent)

def test():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap()

for x in data: heap.push(x)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def testBuildHeap():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap(data)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def main():

test()

testBuildHeap()

if __name__ == '__main__':

main()

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Solution1: Prefix Sum + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

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

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

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

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};

花花酱 LeetCode 1657. Determine if Two Strings Are Close

By zxi on November 14, 2020

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.
- For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example, aacabb -> bbcbaa (all a‘s turn into b‘s, and all b‘s turn into a‘s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 10⁵
word1 and word2 contain only lowercase English letters.

Solution: Hashtable

Two strings are close:
1. Have the same length, ccabbb => 6 == aabccc => 6
2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)
3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)

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

C++

// Author: Huahua

class Solution {

public:

bool closeStrings(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

if (l1 != l2) return false;

vector<int> f1(128), f2(128);

vector<int> s1(128), s2(128);

for (char c: word1) ++f1[c], s1[c] = 1;

for (char c: word2) ++f2[c], s2[c] = 1;

sort(begin(f1), end(f1));

sort(begin(f2), end(f2));

return f1 == f2 && s1 == s2;

}

};

Python3

# Author: Huahua

class Solution:

def closeStrings(self, word1: str, word2: str) -> bool:

c1, c2 = Counter(word1), Counter(word2)

return all([len(word1) == len(word2),

c1.keys() == c2.keys(),

sorted(c1.values()) == sorted(c2.values())])

Huahua's Tech Road

花花酱 LeetCode 1663. Smallest String With A Given Numeric Value

Solution: Greedy, Fill in reverse order

C++

Python3

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

Solution1: Construct the string

C++

Solution 2: Pointers

C++

花花酱 Min Heap SP21

C++

Python3

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

Solution1: Prefix Sum + Hashtable

C++

Solution2: Sliding Window

C++

花花酱 LeetCode 1657. Determine if Two Strings Are Close

Solution: Hashtable

C++

Python3