# Posts tagged as “string”

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 <= 105
• 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)

## Python3

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 <= 103
• 1 <= word1[i].length, word2[i].length <= 103
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
• word1[i] and word2[i] consist of lowercase letters.

## Solution1: Construct the string

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

## Solution 2: Pointers

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

## C++

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 <= 105
• 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)

## Python3

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanceds is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").


Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.


Constraints:

• 1 <= s.length <= 105
• s[i] is 'a' or 'b'​​.

## Solution: DP

dp[i] := min # of dels to make s[0:i] all ‘a’s;
dp[i] := min # of dels to make s[0:i] ends with 0 or mode ‘b’s

if s[i-1] == ‘a’:
dp[i + 1] = dp[i], dp[i + 1] = min(dp[i + 1], dp[i] + 1)
else:
dp[i + 1] = dp[i] + 1, dp[i + 1] = dp[i]

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

## C++

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

Input: s = "aab"
Output: 0
Explanation: s is already good.


Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).


Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

## Solution: Hashtable

The deletion order doesn’t matter, we can process from ‘a’ to ‘z’. Use a hashtable to store the “final frequency” so far, for each char, decrease its frequency until it becomes unique in the final frequency hashtable.

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

## C++

Mission News Theme by Compete Themes.