{"id":7216,"date":"2020-08-09T09:24:37","date_gmt":"2020-08-09T16:24:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7216"},"modified":"2020-08-09T09:25:57","modified_gmt":"2020-08-09T16:25:57","slug":"leetcode-1540-can-convert-string-in-k-moves","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1540-can-convert-string-in-k-moves\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1540. Can Convert String in K Moves"},"content":{"rendered":"\n<p>Given two strings&nbsp;<code>s<\/code>&nbsp;and&nbsp;<code>t<\/code>, your goal is to convert&nbsp;<code>s<\/code>&nbsp;into&nbsp;<code>t<\/code>&nbsp;in&nbsp;<code>k<\/code>moves or less.<\/p>\n\n\n\n<p>During the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;(<code>1 &lt;= i &lt;= k<\/code>)&nbsp;move you can:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose any index&nbsp;<code>j<\/code>&nbsp;(1-indexed) from&nbsp;<code>s<\/code>, such that&nbsp;<code>1 &lt;= j &lt;= s.length<\/code>&nbsp;and&nbsp;<code>j<\/code>&nbsp;has not been chosen in any previous move,&nbsp;and shift the character at that index&nbsp;<code>i<\/code>&nbsp;times.<\/li><li>Do nothing.<\/li><\/ul>\n\n\n\n<p>Shifting a character means replacing it by the next letter in the alphabet&nbsp;(wrapping around so that&nbsp;<code>'z'<\/code>&nbsp;becomes&nbsp;<code>'a'<\/code>). Shifting a character by&nbsp;<code>i<\/code>&nbsp;means applying the shift operations&nbsp;<code>i<\/code>&nbsp;times.<\/p>\n\n\n\n<p>Remember that any index&nbsp;<code>j<\/code>&nbsp;can be picked at most once.<\/p>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;if it&#8217;s possible to convert&nbsp;<code>s<\/code>&nbsp;into&nbsp;<code>t<\/code>&nbsp;in no more than&nbsp;<code>k<\/code>&nbsp;moves, otherwise return&nbsp;<code>false<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"input\", t = \"ouput\", k = 9\n<strong>Output:<\/strong> true\n<strong>Explanation: <\/strong>In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"abc\", t = \"bcd\", k = 10\n<strong>Output:<\/strong> false\n<strong>Explanation: <\/strong>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.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"aab\", t = \"bbb\", k = 27\n<strong>Output:<\/strong> true\n<strong>Explanation: <\/strong>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'.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length, t.length &lt;= 10^5<\/code><\/li><li><code>0 &lt;= k &lt;= 10^9<\/code><\/li><li><code>s<\/code>,&nbsp;<code>t<\/code>&nbsp;contain&nbsp;only lowercase English letters.<\/li><\/ul>\n\n\n\n<p><strong>Solution: HashTable<\/strong><\/p>\n\n\n\n<p>Count how many times a d-shift has occurred. <br>a -> c is a 2-shift, z -> b is also 2-shift<br>a -> d is a 3-shift<br>a -> a is a 0-shift that we can skip<br>if a d-shift happened for the first time, we need at least d moves<br>However, if it happened for c times, we need at least d + 26 * c moves<br>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.<br>Need to find maximum move we need and make sure that one is &lt;= k.<br>Since we can pick any index to shift, so the order doesn&#8217;t matter. We can start from left to right.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(26) = O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool canConvertString(string s, string t, int k) {\n    if (s.length() != t.length()) return false;\n    vector<int> count(26);    \n    for (int i = 0; i < s.length(); ++i) {            \n      int d = (t[i] - s[i] + 26) % 26;\n      int c = count[d]++;\n      if (d != 0 &#038;&#038; d + c * 26 > k)\n        return false;\n    }    \n    return true;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two strings&nbsp;s&nbsp;and&nbsp;t, your goal is to convert&nbsp;s&nbsp;into&nbsp;t&nbsp;in&nbsp;kmoves or less. During the&nbsp;ith&nbsp;(1 &lt;= i &lt;= k)&nbsp;move you can: Choose any index&nbsp;j&nbsp;(1-indexed) from&nbsp;s, such that&nbsp;1 &lt;=&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177,309,4],"class_list":["post-7216","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","tag-shift","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7216","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7216"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7216\/revisions"}],"predecessor-version":[{"id":7218,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7216\/revisions\/7218"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}