{"id":5450,"date":"2019-08-18T09:01:27","date_gmt":"2019-08-18T16:01:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5450"},"modified":"2019-08-18T09:51:20","modified_gmt":"2019-08-18T16:51:20","slug":"leetcode-1163-last-substring-in-lexicographical-order","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1163-last-substring-in-lexicographical-order\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1163. Last Substring in Lexicographical Order"},"content":{"rendered":"\n

Given a string s<\/code>, return the last substring of s<\/code> in lexicographical order.<\/p>\n\n\n\n

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

Input: <\/strong>\"abab\"\nOutput: <\/strong>\"bab\"\nExplanation: <\/strong>The substrings are [\"a\", \"ab\", \"aba\", \"abab\", \"b\", \"ba\", \"bab\"]. The lexicographically maximum substring is \"bab\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>\"leetcode\"\nOutput: <\/strong>\"tcode\"\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= s.length <= 10^5<\/code><\/li>
  2. s contains only lowercase English letters.<\/li><\/ol>\n\n\n\n
    Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
    e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”<\/p>\n\n\n\n
    Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n
    Try all possible suffixes.
    Time complexity: O(n^2)
    Space complexity: O(1)
    <\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, 452 ms, 12.8 MB\nclass Solution {\npublic:\n  string lastSubstring(string_view s) {\n    string_view ans;\n    for (int i = 0; i < s.length(); ++i)\n      if (s.substr(i) > ans) ans = s.substr(i);\n    return string(ans);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Keep max and compare with candidates<\/strong><\/h2>\n\n\n\n
    Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.<\/p>\n\n\n\n
    e.g. “acbacbc”<\/p>\n\n\n\n
     “c” > “a”, the first “c” becomes the best.
    “c” = “c”, the second “c” becomes a candidate
    starting compare best and candidate.
    “cb” = “cb”
    “cba” < “cbc”, cand_i is the new best.
    <\/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  string lastSubstring(string s) {\n    int max_i = 0;\n    char max_c = 0;\n    int cand_i = 0;\n    int l = 0;\n    \n    for (int i = 0; i < s.length(); ++i) {\n      if (s[i] > max_c) {\n        \/\/ Find a better starting point.\n        max_c = s[i];\n        max_i = i;\n        cand_i = -1;\n        l = 1;\n      } else if (cand_i != -1) {\n        \/\/ Has a candidate.\n        if (s[i] > s[max_i + l]) {\n          \/\/ The candidate is larger.\n          max_i = cand_i;\n          cand_i = -1;\n        } else if (s[i] == s[max_i + l]) {\n          \/\/ The candidate is the same as current best.\n          ++l;\n        } else {\n          \/\/ The candidate is smaller, no longer needed.\n          cand_i = -1;\n        }\n      } else if (s[i] == max_c) {\n        \/\/ Find a new candidate, starting with length 1.\n        cand_i = i;\n        l = 1;\n      } \n    }\n    \n    return s.substr(max_i);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a string s, return the last substring of s in lexicographical order. Example 1: Input: “abab” Output: “bab” Explanation: The substrings are [“a”, “ab”, “aba”, “abab”, “b”,…<\/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":[217,186],"class_list":["post-5450","post","type-post","status-publish","format-standard","hentry","category-string","tag-hard","tag-suffix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5450","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=5450"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5450\/revisions"}],"predecessor-version":[{"id":5453,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5450\/revisions\/5453"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5450"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}