# LeetCode Find Kth Bit in Nth Binary String

5484. Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

• S1 = "0"
• Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".


Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".


Example 3:

Input: n = 1, k = 1
Output: "0"


Example 4:

Input: n = 2, k = 3
Output: "1"


Constraints:

• 1 <= n <= 20
• 1 <= k <= 2n - 1

class Solution {
private:
string InvertStr(string &s) {
string ans = "";
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '0')ans.push_back('1');
else ans.push_back('0');
}
return ans;
}
public:
char findKthBit(int n, int k) {
string s = "0";
for (int i = 2; i <= n; ++i) {
string inv_str = InvertStr(s);
reverse(inv_str.begin(), inv_str.end());
s = s + "1" + inv_str;
}
return s[k - 1];
}
};

# LeetCode Shuffle String

5472. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.


Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.


Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"


Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"


Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"


Constraints:

• s.length == indices.length == n
• 1 <= n <= 100
• s contains only lower-case English letters.
• 0 <= indices[i] < n
• All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

class Solution {
public:
string restoreString(string s, vector<int>& indices) {
int n = s.size();
string ans = s;
for (int i = 0; i < n; ++i)ans[indices[i]] = s[i];
return ans;
}
};

# LeetCode Number of Substrings With Only 1s

1513. Number of Substrings With Only 1s

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.


Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.


Example 4:

Input: s = "000"
Output: 0


Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

const long long kMOD = 1e9 + 7;

class Solution {
long long CalAccSum(long long l) {
return (l %kMOD)* ((l + 1) % kMOD) / 2;
}
public:
int numSub(string s) {

long long ans = 0;
int i = 0, j = 0, n = s.size();
while (i < n) {
while (i < n&&s[i] == '0')++i;
if (i >= n)break;
j = i + 1;
while (j < n&&s[j] == '1')++j;
int m = j - i;
ans += CalAccSum(m) % kMOD;
i = j;
}
return ans % kMOD;
}
};

# 剑指 Offer 05. 替换空格

0 <= s 的长度 <= 10000

class Solution {
public:
string replaceSpace(string s) {
string ans = "";
for(int i = 0; i < s.size(); ++i) {
if(s[i] == ' ') ans += "%20";
else ans += s[i];
}
return ans;
}
};

# LeetCode Making File Names Unique

1487. Making File Names Unique

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"


Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"


Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".


Example 4:

Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".


Example 5:

Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.


Constraints:

• 1 <= names.length <= 5 * 10^4
• 1 <= names[i].length <= 20
• names[i] consists of lower case English letters, digits and/or round brackets.

class Solution {
public:
vector<string> getFolderNames(vector<string>& names) {
vector<string> ans;
unordered_map<string, int> show_times;
for (int i = 0; i < names.size(); ++i) {
if (show_times.find(names[i]) == show_times.end()) {
ans.push_back(names[i]);
show_times[names[i]] = 1;
}
else {
int k = show_times[names[i]];
string next_name = names[i] + "(" + to_string(k) + ")";
while (show_times.find(next_name) != show_times.end()) {
show_times[names[i]] = ++k;
next_name = names[i] + "(" + to_string(k) + ")";
}
ans.push_back(next_name);
show_times[next_name] = 1;
}
}
return ans;
}
};

# LeetCode Check If a Word Occurs As a Prefix of Any Word in a Sentence

5416. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.


Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.


Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.


Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4


Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1


Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
int idx = 1, i = 0, j = 0, n = sentence.size();
while (i < n) {
j = i + 1;
while (j < n&&sentence[j] != ' ')++j;
string cur = sentence.substr(i, j - i);
size_t pos = cur.find(searchWord);
if (pos != string::npos&&pos == 0) {
return idx;
}
++idx;
i = j + 1;
}
return -1;
}
};


# LeetCode Display Table of Food Orders in a Restaurant

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant’s “display table. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]]
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito".


Example 2:

Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
Output: [["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]]
Explanation:
For the table 1: Adam and Brianna order "Canadian Waffles".
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".


Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]


Constraints:

• 1 <= orders.length <= 5 * 10^4
• orders[i].length == 3
• 1 <= customerNamei.length, foodItemi.length <= 20
• customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character.
• tableNumberi is a valid integer between 1 and 500.

class Solution {
public:
vector<vector<string>> displayTable(vector<vector<string>>& orders) {
vector<map<string, int>> tables(501, map<string, int>());
set<string> allfoods;
for (int i = 0; i < orders.size(); ++i) {
string name = orders[i][0], tb = orders[i][1], food = orders[i][2];
int ntb = stoi(tb.c_str());
++tables[ntb][food];
allfoods.insert(food);
}
vector<vector<string>> ans;
for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it)header.push_back(*it);
for (int i = 1; i <= 500; ++i) {
vector<string> cur;
if (tables[i].size() > 0) {
cur.push_back(to_string(i));
for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it) {
cur.push_back(to_string(tables[i][*it]));
}
ans.push_back(cur);
}
}
return ans;
}
};


# LeetCode Reformat The String

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.

class Solution {
public:
string reformat(string s) {
string alpha = "", digit = "";
for (int i = 0; i < s.size(); ++i) {
if (s[i] >= '0'&&s[i] <= '9')digit.push_back(s[i]);
else alpha.push_back(s[i]);
}

int a = alpha.size(), d = digit.size();
if (abs(a - d) >= 2)return "";
string ans = "";
int i = 0, j = 0;
if (a > d) {
while (i < a || j < d) {
ans.push_back(alpha[i++]);
if (j < d)ans.push_back(digit[j++]);
}
}
else {
while (i < a || j < d) {
ans.push_back(digit[j++]);
if (i < a)ans.push_back(alpha[i++]);
}
}
return ans;
}
};

# LeetCode Valid Parenthesis String

678. Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True


Example 2:

Input: "(*)"
Output: True


Example 3:

Input: "(*))"
Output: True


Note:

1. The string size will be in the range [1, 100].

class Solution {
public:
bool checkValidString(string s) {
int left_balance = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '*')++left_balance;
else --left_balance;
if (left_balance < 0)return false;
}
if (left_balance == 0)return true;

int right_balance = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == ')' || s[i] == '*')++right_balance;
else --right_balance;
if (right_balance < 0)return false;
}
return true;
}
};

class Solution {
public:
bool checkValidString(string s) {
int min_left = 0, max_left = 0;
for (int i = 0; i < s.size(); ++i) {
min_left += (s[i] == '(' ? 1 : -1);
max_left += (s[i] != ')' ? 1 : -1);
if (max_left < 0)break;
min_left = max(min_left, 0);
}
return min_left == 0;
}
};

# LeetCode Perform String Shifts

LeetCode Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

• direction can be 0 (for left shift) or 1 (for right shift).
• amount is the amount by which string s is to be shifted.
• A left shift by 1 means remove the first character of s and append it to the end.
• Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation:
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:

• 1 <= s.length <= 100
• s only contains lower case English letters.
• 1 <= shift.length <= 100
• shift[i].length == 2
• 0 <= shift[i][0] <= 1
• 0 <= shift[i][1] <= 100

class Solution {
public:
string stringShift(string s, vector<vector<int>>& shift) {
int left = 0, right = 0, n = s.size();
for (int i = 0; i < shift.size(); ++i) {
if (shift[i][0] == 0)left += shift[i][1];
else right += shift[i][1];
}
if (left > right) {
left -= right;
left %= n;
return s.substr(left) + s.substr(0, left);
}
else if (right > left) {
right -= left;
right %= n;
return s.substr(n - right) + s.substr(0, n - right);
}
else {
return s;
}
}
};