the second one in Biweekly Contest 32.
Difficulty : Medium
Related Topics : String、Greedy
Given two strings
s
andt
, your goal is to converts
intot
ink
moves or less.During the
i
th
(1 <= i <= k
) move you can:Choose any index
j
(1-indexed) from s, such that1 <= j <= s.length
andj
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 converts
intot
in no more thank
moves, otherwise returnfalse
.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'.
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.
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'.
1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s
,t
contain only lowercase English letters.
- mine
- Java
Runtime: 10 ms, faster than 100.00%, Memory Usage: 39.9 MB, less than 100.00% of Java online submissions
// O(N)time // O(1)space public boolean canConvertString(String s, String t, int k) { if (s.length() != t.length()) return false; int n = s.length(); int[] record = new int[26]; int max = 0; for (int i = 0; i < n; i++) { int m = t.charAt(i) - s.charAt(i); if (m == 0) continue; if (m < 0) { m += 26; } max = Math.max(max, record[m] * 26 + m); record[m]++; } return k >= max; }
- Java
- the most votes
Runtime: 17 ms, faster than 100.00%, Memory Usage: 40.1 MB, less than 100.00% of Java online submissions
// O(N)time // O(1)space public boolean canConvertString(String s, String t, int k) { if (s.length() != t.length()) { return false; } int[] count = new int[26]; for (int i = 0; i < s.length(); ++i) { int diff = (t.charAt(i) - s.charAt(i) + 26) % 26; if (diff > 0 && diff + count[diff] * 26 > k) { return false; } ++count[diff]; } return true; }