Problem Statement
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.
Find and return the length of the shortest superstring of a, b, c, and d.
Definition
- Class:
- FourStrings
- Method:
- shortestLength
- Parameters:
- String, String, String, String
- Returns:
- int
- Method signature:
- int shortestLength(String a, String b, String c, String d)
- (be sure your method is public)
Constraints
- a will contain between 1 and 10 characters, inclusive.
- b will contain between 1 and 10 characters, inclusive.
- c will contain between 1 and 10 characters, inclusive.
- d will contain between 1 and 10 characters, inclusive.
- Each character in a will be a lowercase English letter ('a'-'z').
- Each character in b will be a lowercase English letter ('a'-'z').
- Each character in c will be a lowercase English letter ('a'-'z').
- Each character in d will be a lowercase English letter ('a'-'z').
Examples
"abc"
"ab"
"bc"
"b"
Returns: 3
The shortest superstring in this test case is the string "abc". Note that each of the other three strings occurs in "abc" as a contiguous substring.
"a"
"bc"
"def"
"ghij"
Returns: 10
In this case, one possible shortest superstring is "abcdefghij".
"top"
"coder"
"opco"
"pcode"
Returns: 8
S = "topcoder"
"thereare"
"arelots"
"lotsof"
"ofcases"
Returns: 19
"aba"
"b"
"b"
"b"
Returns: 3
"x"
"x"
"x"
"x"
Returns: 1
"aaabab"
"ba"
"bbabab"
"bbbbab"
Returns: 13
"aaaaa"
"a"
"aaaaaaaaaa"
"aaaa"
Returns: 10
"aaaaaaaaaa"
"bbbbbbbbbb"
"cccccccccc"
"dddddddddd"
Returns: 40
"abbabadbd"
"bsddsbdsd"
"bas"
"d"
Returns: 21
"aba"
"b"
"b"
"b"
Returns: 3
"ba"
"a"
"bbb"
"a"
Returns: 4
"bbb"
"baaa"
"bbb"
"bbab"
Returns: 8
"a"
"aa"
"b"
"aabb"
Returns: 4
"a"
"bbba"
"ba"
"aa"
Returns: 5
"bbbbba"
"babaaa"
"aab"
"abaabab"
Returns: 15
"ba"
"babab"
"abb"
"abbb"
Returns: 7
"a"
"ab"
"bb"
"bb"
Returns: 3
"baabbab"
"ababbaaa"
"bbb"
"babbaaa"
Returns: 15
"abbbb"
"abbbaaa"
"bb"
"abaaabb"
Returns: 15
"ba"
"babb"
"b"
"bb"
Returns: 4
"b"
"aa"
"b"
"a"
Returns: 3
"bbabbbb"
"ba"
"ababa"
"aaab"
Returns: 14
"bbcaa"
"acbc"
"cccc"
"aa"
Returns: 11
"bbca"
"bccaacbcac"
"bac"
"aa"
Returns: 17
"acaa"
"c"
"babaa"
"aab"
Returns: 9
"ac"
"b"
"bab"
"acc"
Returns: 6
"cbaacca"
"aaaabcb"
"b"
"bb"
Returns: 14
"c"
"baa"
"abbc"
"b"
Returns: 6
"ba"
"bacca"
"babbc"
"bcabbaaa"
Returns: 16
"acbc"
"abbabcc"
"bacac"
"acbaa"
Returns: 18
"c"
"c"
"cb"
"cc"
Returns: 3
"aaccb"
"baa"
"a"
"abbabc"
Returns: 12
"vkd"
"q"
"zhowey"
"yqkcvhp"
Returns: 15
"h"
"e"
"m"
"wjri"
Returns: 7
"eduu"
"i"
"htba"
"chn"
Returns: 12
"k"
"e"
"h"
"l"
Returns: 4
"pae"
"sbsg"
"mqjho"
"e"
Returns: 12
"hsf"
"ojdx"
"pcvhx"
"th"
Returns: 13
"c"
"uu"
"i"
"qp"
Returns: 6
"egnxvve"
"v"
"meqqn"
"ixspgyhscc"
Returns: 22
"loz"
"bzlk"
"cjrxm"
"oi"
Returns: 14
"akdh"
"rpsb"
"dd"
"w"
Returns: 11
"ab"
"j"
"de"
"bcd"
Returns: 6
"aaaaaaaaab"
"aaaaaaaaac"
"aaaaaaaaad"
"aaaaaaaaae"
Returns: 40
"topcod"
"coder"
"codcod"
"ret"
Returns: 13
"arelots"
"thereare"
"lotsof"
"cases"
Returns: 19
"dfdsfhfsdg"
"uiodsfhfnb"
"dfbwefeqpe"
"fhudsfhqwn"
Returns: 40
"kl"
"ly"
"arkly"
"klya"
Returns: 6
"ab"
"bd"
"ba"
"ac"
Returns: 6
"abc"
"cba"
"aad"
"diefur"
Returns: 12
"coder"
"pcode"
"top"
"opco"
Returns: 8
"abc"
"ab"
"ab"
"ab"
Returns: 3
"d"
"dxxxxxxxxx"
"exxxxxxxxx"
"x"
Returns: 20
"abcdefghi"
"efb"
"hiabcd"
"hiabcz"
Returns: 18
"abc"
"ghij"
"ceg"
"egh"
Returns: 8
"abab"
"abc"
"bcb"
"bcd"
Returns: 8
"abcd"
"def"
"cddef"
"ef"
Returns: 7
"abb"
"bbc"
"bbb"
"bbb"
Returns: 5
"thereare"
"lotso"
"ofca"
"cases"
Returns: 19
"ef"
"e"
"cd"
"ab"
Returns: 6
"abc"
"b"
"d"
"e"
Returns: 5
"thereare"
"sothere"
"ere"
"reare"
Returns: 10
"abcd"
"abcd"
"cdabcd"
"abcdab"
Returns: 8
"asgrgrrr"
"sadrgdas"
"ferrrred"
"we"
Returns: 24
"ab"
"bc"
"abdef"
"a"
Returns: 7
"ab"
"cd"
"bdc"
"e"
Returns: 6
"abc"
"bcdy"
"dba"
"xab"
Returns: 9
"abcd"
"bcde"
"cdbc"
"qqqq"
Returns: 12
"ab"
"c"
"bf"
"gh"
Returns: 6
"abcratabc"
"rat"
"rat"
"rat"
Returns: 9
"abcde"
"ac"
"ad"
"bd"
Returns: 11
"abc"
"b"
"xyz"
"y"
Returns: 6
"abc"
"ae"
"abckae"
"a"
Returns: 6