{"id":6689,"date":"2020-05-03T19:44:11","date_gmt":"2020-05-04T02:44:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6689"},"modified":"2020-05-03T19:44:12","modified_gmt":"2020-05-04T02:44:12","slug":"leetcode-1433-check-if-a-string-can-break-another-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1433-check-if-a-string-can-break-another-string\/","title":{"rendered":"LeetCode 1433. Check If a String Can Break Another String"},"content":{"rendered":"\n

Given two strings: s1<\/code> and s2<\/code> with the same size, check if some permutation of string s1<\/code> can break some permutation of string s2<\/code> or vice-versa (in other words s2<\/code> can break s1<\/code>).<\/p>\n\n\n\n

A string x<\/code> can break string y<\/code> (both of size n<\/code>) if x[i] >= y[i]<\/code> (in alphabetical order) for all i<\/code> between 0<\/code> and n-1<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s1 = \"abc\", s2 = \"xya\"\nOutput:<\/strong> true\nExplanation:<\/strong> \"ayx\" is a permutation of s2=\"xya\" which can break to string \"abc\" which is a permutation of s1=\"abc\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s1 = \"abe\", s2 = \"acd\"\nOutput:<\/strong> false \nExplanation:<\/strong> All permutations for s1=\"abe\" are: \"abe\", \"aeb\", \"bae\", \"bea\", \"eab\" and \"eba\" and all permutation for s2=\"acd\" are: \"acd\", \"adc\", \"cad\", \"cda\", \"dac\" and \"dca\". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s1 = \"leetcodee\", s2 = \"interview\"\nOutput:<\/strong> true\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • s1.length == n<\/code><\/li>
  • s2.length == n<\/code><\/li>
  • 1 <= n <= 10^5<\/code><\/li>
  • All strings consist of lowercase English letters.<\/li><\/ul>\n\n\n\n
    Solution 1: Sort and compare<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool checkIfCanBreak(string s1, string s2) {\n    sort(begin(s1), end(s1));\n    sort(begin(s2), end(s2));\n    \n    int f1 = 1;\n    int f2 = 1;\n    for (int i = 0; i < s1.size(); ++i) {\n      f1 &= s1[i] <= s2[i];\n      f2 &= s1[i] >= s2[i];\n    }\n    \n    return f1 || f2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Counting Sort<\/strong><\/h2>\n\n\n\n
    The cumulative number of elements must be monotonic e.g. t1 >= t2 or t2 >= t1 for all the letters.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool checkIfCanBreak(string s1, string s2) {\n    vector c1(26);\n    vector c2(26);\n    for (int i = 0; i < s1.length(); ++i) {\n      ++c1[s1[i] - 'a'];\n      ++c2[s2[i] - 'a'];\n    }\n    \n    int t1 = 0;\n    int t2 = 0;\n    int f1 = 1;\n    int f2 = 1;\n    for (int i = 0; i < 26; ++i) {\n      t1 += c1[i];\n      t2 += c2[i];\n      f1 &= t1 <= t2;\n      f2 &= t2 <= t1;\n    }\n    \n    return f1 || f2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa (in other words s2 can break s1). A string x can break string y (both of size n) if x[i] >=…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[],"class_list":["post-6689","post","type-post","status-publish","format-standard","hentry","category-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6689","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=6689"}],"version-history":[{"count":1,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6689\/revisions"}],"predecessor-version":[{"id":6690,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6689\/revisions\/6690"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6689"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6689"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}