Posts tagged as “hashtable”

花花酱 LeetCode 1542. Find Longest Awesome Substring

By zxi on August 10, 2020

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

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

C++

class Solution {

public:

int longestAwesome(string s) {

constexpr int kInf = 1e9;

vector<int> idx(1024, kInf);

idx[0] = -1;

int mask = 0; // prefix's state 0:even, 1:odd

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

mask ^= (1 << (s[i] - '0'));

ans = max(ans, i - idx[mask]);

// One digit with odd count is allowed.

for (int j = 0; j < 10; ++j)

ans = max(ans, i - idx[mask ^ (1 << j)]);

idx[mask] = min(idx[mask], i);

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int longestAwesome(String s) {

final int n = s.length();

int[] idx = new int[1024];

Arrays.fill(idx, n);

idx[0] = -1;

int mask = 0;

int ans = 0;

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

mask ^= (1 << (s.charAt(i) - '0'));

ans = Math.max(ans, i - idx[mask]);

for (int j = 0; j < 10; ++j)

ans = Math.max(ans,

i - idx[mask ^ (1 << j)]);

idx[mask] = Math.min(idx[mask], i);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

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

idx = [-1] + [len(s)] * 1023

ans, mask = 0, 0

for i, c in enumerate(s):

mask ^= 1 << (ord(c) - ord('0'))

ans = max([ans, i - idx[mask]]

+ [i - idx[mask ^ (1 << j)] for j in range(10)])

idx[mask] = min(idx[mask], i)

return ans

花花酱 LeetCode 1540. Can Convert String in K Moves

By zxi on August 9, 2020

Given two strings s and t, your goal is to convert s into t in kmoves or less.

During the i^th (1 <= i <= k) move you can:

Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it’s possible to convert s into t in no more than k moves, otherwise return false.

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.

Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s, t contain only lowercase English letters.

Solution: HashTable

Count how many times a d-shift has occurred.
a -> c is a 2-shift, z -> b is also 2-shift
a -> d is a 3-shift
a -> a is a 0-shift that we can skip
if a d-shift happened for the first time, we need at least d moves
However, if it happened for c times, we need at least d + 26 * c moves
e.g. we can do a 2-shift at the 2nd move, do another one at 2 + 26 = 28th move and do another at 2 + 26*2 = 54th move, and so on.
Need to find maximum move we need and make sure that one is <= k.
Since we can pick any index to shift, so the order doesn’t matter. We can start from left to right.

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

C++

// Author: Huahua

class Solution {

public:

bool canConvertString(string s, string t, int k) {

if (s.length() != t.length()) return false;

vector<int> count(26);

for (int i = 0; i < s.length(); ++i) {

int d = (t[i] - s[i] + 26) % 26;

int c = count[d]++;

if (d != 0 && d + c * 26 > k)

return false;

}

return true;

}

};

花花酱 LeetCode 1539. Kth Missing Positive Number

By zxi on August 9, 2020

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the k^th positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

unordered_set<int> s(begin(arr), end(arr));

for (int i = 1; i <= arr.back(); ++i) {

if (!s.count(i)) --k;

if (k == 0) return i;

}

return arr.back() + k;

}

};

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

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

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

int l = 0;

int r = arr.size();

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

};

Java

class Solution {

public int findKthPositive(int[] arr, int k) {

int l = 0;

int r = arr.length;

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

Python3

class Solution:

def findKthPositive(self, arr: List[int], k: int) -> int:

l, r = 0, len(arr)

while l < r:

m = l + (r - l) // 2

if arr[m] - (m + 1) >= k:

r = m

else:

l = m + 1

return l + k

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

function<void(int)> postOrder = [&](int i) {

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

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

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans

花花酱 LeetCode 1507. Reformat Date

By zxi on July 11, 2020

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Solution: String + HashTable

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

C++

// Author: Huahua

class Solution {

public:

string reformatDate(string date) {

stringstream ss(date);

string day, month, year;

ss >> day >> month >> year;

unordered_map<string, string> m{{"Jan", "01"},

{"Feb", "02"},

{"Mar", "03"},

{"Apr", "04"},

{"May", "05"},

{"Jun", "06"},

{"Jul", "07"},

{"Aug", "08"},

{"Sep", "09"},

{"Oct", "10"},

{"Nov", "11"},

{"Dec", "12"}};

day = day.substr(0, day.length() - 2);

if (day.length() == 1) day = "0" + day;

return year + "-" + m[month] + "-" + day;

}

};

Java

// Author: Huahua

class Solution {

public String reformatDate(String date) {

Map<String, String> m = new HashMap<String, String>();

m.put("Jan", "01");

m.put("Feb", "02");

m.put("Mar", "03");

m.put("Apr", "04");

m.put("May", "05");

m.put("Jun", "06");

m.put("Jul", "07");

m.put("Aug", "08");

m.put("Sep", "09");

m.put("Oct", "10");

m.put("Nov", "11");

m.put("Dec", "12");

String[] items = date.split(" ");

String day = items[0].substring(0, items[0].length() - 2);

if (day.length() == 1) day = "0" + day;

return items[2] + "-" + m.get(items[1]) + "-" + day;

}

Python

# Author: Huahua

class Solution:

def reformatDate(self, date: str) -> str:

m = {"Jan": "01", "Feb": "02", "Mar": "03",

"Apr": "04", "May": "05", "Jun": "06",

"Jul": "07", "Aug": "08", "Sep": "09",

"Oct": "10", "Nov": "11", "Dec": "12"}

items = date.split(" ")

day = items[0][:-2]

if len(day) == 1: day = "0" + day

return items[2] + "-" + m[items[1]] + "-" + day