A. Mahmoud and Longest Uncommon Subsequence

Codeforces

IDCF766A

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsstrings

English · Original

Chinese · Translation

Formal · Original

While Mahmoud and Ehab were practicing for IOI, they found a problem which name was Longest common subsequence. They solved it, and then Ehab challenged Mahmoud with another problem. Given two strings _a_ and _b_, find the length of their longest uncommon subsequence, which is the longest string that is a subsequence of one of them and not a subsequence of the other. A subsequence of some string is a sequence of characters that appears in the same order in the string, The appearances don't have to be consecutive, for example, strings "_ac_", "_bc_", "_abc_" and "_a_" are subsequences of string "_abc_" while strings "_abbc_" and "_acb_" are not. The empty string is a subsequence of any string. Any string is a subsequence of itself. ## Input The first line contains string _a_, and the second line — string _b_. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is not bigger than 105 characters. ## Output If there's no uncommon subsequence, print "_\-1_". Otherwise print the length of the longest uncommon subsequence of _a_ and _b_. [samples] ## Note In the first example: you can choose "_defgh_" from string _b_ as it is the longest subsequence of string _b_ that doesn't appear as a subsequence of string _a_.

当 Mahmoud 和 Ehab 在为 IOI 练习时，他们遇到了一个名为“最长公共子序列”的问题。他们解决了它，然后 Ehab 给 Mahmoud 提出了另一个问题。给定两个字符串 #cf_span[a] 和 #cf_span[b]，求它们的最长不公共子序列的长度，即最长的字符串，它是其中一个字符串的子序列，但不是另一个字符串的子序列。某个字符串的子序列是指按相同顺序出现在该字符串中的字符序列，这些字符的出现不必连续，例如，字符串 "_ac_"、"_bc_"、"_abc_" 和 "_a_" 都是字符串 "_abc_" 的子序列，而字符串 "_abbc_" 和 "_acb_" 则不是。空字符串是任意字符串的子序列。任意字符串都是它自身的子序列。第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且由英文小写字母组成。每个字符串的长度不超过 #cf_span[105] 个字符。如果没有不公共子序列，请输出 "_-1_"。否则，请输出 #cf_span[a] 和 #cf_span[b] 的最长不公共子序列的长度。在第一个例子中：你可以从字符串 #cf_span[b] 中选择 "_defgh_"，因为它是字符串 #cf_span[b] 的最长子序列，且不是字符串 #cf_span[a] 的子序列。 ## Input 第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且由英文小写字母组成。每个字符串的长度不超过 #cf_span[105] 个字符。 ## Output 如果没有不公共子序列，请输出 "_-1_"。否则，请输出 #cf_span[a] 和 #cf_span[b] 的最长不公共子序列的长度。 [samples] ## Note 在第一个例子中：你可以从字符串 #cf_span[b] 中选择 "_defgh_"，因为它是字符串 #cf_span[b] 的最长子序列，且不是字符串 #cf_span[a] 的子序列。

Let $ a $ and $ b $ be two non-empty strings over the lowercase English alphabet. Define: - $ \text{Sub}(s) $: the set of all subsequences of string $ s $. - An *uncommon subsequence* of $ a $ and $ b $ is a string $ x $ such that $ x \in \text{Sub}(a) \setminus \text{Sub}(b) $ or $ x \in \text{Sub}(b) \setminus \text{Sub}(a) $. - The *longest uncommon subsequence* is the longest such $ x $. Objective: Find $ \max \{ |x| \mid x \in (\text{Sub}(a) \setminus \text{Sub}(b)) \cup (\text{Sub}(b) \setminus \text{Sub}(a)) \} $. If the set is empty, output $ -1 $. --- **Key Observation:** The entire string $ a $ is a subsequence of itself. If $ a \neq b $, then $ a \in \text{Sub}(a) \setminus \text{Sub}(b) $ (since $ a $ is not a subsequence of $ b $ if $ a \neq b $), and similarly $ b \in \text{Sub}(b) \setminus \text{Sub}(a) $. Thus, if $ a \neq b $, then the longest uncommon subsequence has length $ \max(|a|, |b|) $. If $ a = b $, then $ \text{Sub}(a) = \text{Sub}(b) $, so the set of uncommon subsequences is empty → output $ -1 $. --- **Formal Solution:** $$ \text{Answer} = \begin{cases} \max(|a|, |b|) & \text{if } a \ne b \\ -1 & \text{if } a = b \end{cases} $$

Samples

Input #1

abcd
defgh

Output #1

Input #2

a
a

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "A. Mahmoud and Longest Uncommon Subsequence",
    "description": {
      "content": "While Mahmoud and Ehab were practicing for IOI, they found a problem which name was Longest common subsequence. They solved it, and then Ehab challenged Mahmoud with another problem. Given two string",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF766A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "While Mahmoud and Ehab were practicing for IOI, they found a problem which name was Longest common subsequence. They solved it, and then Ehab challenged Mahmoud with another problem.\n\nGiven two string...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "当 Mahmoud 和 Ehab 在为 IOI 练习时，他们遇到了一个名为“最长公共子序列”的问题。他们解决了它，然后 Ehab 给 Mahmoud 提出了另一个问题。\n\n给定两个字符串 #cf_span[a] 和 #cf_span[b]，求它们的最长不公共子序列的长度，即最长的字符串，它是其中一个字符串的子序列，但不是另一个字符串的子序列。\n\n某个字符串的子序列是指按相同顺序出现在该字符串中的字...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a $ and $ b $ be two non-empty strings over the lowercase English alphabet.\n\nDefine:\n- $ \\text{Sub}(s) $: the set of all subsequences of string $ s $.\n- An *uncommon subsequence* of $ a $ and $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments