Problem Statement
You are given an
Two strings of length L are called completely different if they differ at every index. For example, X="abcd" and Y="bcda" are completely different but X="frog" and Y="plow" are not because X[2] = Y[2] = 'o'.
Compute and return the total number of strings with the following properties:
- The length of the string is L. (That is, its length is the same as the length of the strings in forbidden.)
- Each character of the string is one of the first S lowercase English letters.
- The string is completely different from every string in forbidden.
Definition
- Class:
- CompletelyDifferentStrings
- Method:
- count
- Parameters:
- int, String[]
- Returns:
- int
- Method signature:
- int count(int S, String[] forbidden)
- (be sure your method is public)
Constraints
- S will be between 1 and 26, inclusive.
- forbidden will contain between 1 and 30 elements, inclusive.
- All elements of forbidden will have the same length L.
- L will be between 1 and 6, inclusive.
- Each character in each element of forbidden will be one of the first S lowercase English letters.
Examples
3
{"ab"}
Returns: 4
As S = 3, we are only using the first three lowercase English letters: 'a', 'b', and 'c'. We are looking for strings of length 2 that are completely different from "ab". There are four such strings: "ba", "bc", "ca", and "cc".
1
{"aaaaa", "aaaaa"}
Returns: 0
The only string of length 5 is "aaaaa", but this string is not completely different from the (identical) forbidden string "aaaaa". Thus, there are no strings with all the properties we need.
2
{"ababa", "babab"}
Returns: 0
2
{"ababa", "abbba"}
Returns: 0
7
{"baba", "babe", "cage", "cafe", "feed", "deed", "deaf", "dead"}
Returns: 90
3
{"abacaa", "abacaa", "acabab"}
Returns: 8
Note that the strings in forbidden are not necessarily distinct.
26
{"aaaaaa"}
Returns: 244140625
12
{"hjfei", "ggjag", "kabae", "hliaf", "jgddi", "ifhda", "ifllf", "jfijd", "dlacf", "bfjgi", "iebkd", "lfdhl", "bgjfk", "edief"}
Returns: 480
18
{"miq", "hdg", "mpi", "reo", "afr", "cci", "qrp", "nlb", "iqp", "kah", "gln", "ffp", "ged", "elq", "mdi", "oad"}
Returns: 320
14
{"e", "a", "c", "c", "l", "i", "n", "h", "d", "m", "m", "m"}
Returns: 5
16
{"acfek", "bhbmd", "acjbj", "heicp", "kbdnn"}
Returns: 191664
12
{"jcbi", "bhkh", "agji", "belh", "ibdf"}
Returns: 3528
26
{"asdv", "ooiu"}
Returns: 331776
18
{"jb", "ir", "pm", "cd", "qp", "rl", "jn", "gc", "dq", "jm", "kr", "ld", "cn", "lb", "lb", "mi", "ig", "jg"}
Returns: 49
15
{"fnka", "cjha", "agnh", "ihjn"}
Returns: 15972
9
{"bcg"}
Returns: 512
11
{"ij", "ie", "fi", "aj"}
Returns: 64
22
{"ttotr", "fvmbf", "tftcp", "nbhof", "tmate"}
Returns: 1779084
24
{"ampx", "oulx", "dqmd", "cnnr", "dtfv", "ppot", "cmqq", "knxg", "kmce", "wpku", "udip", "clam", "tcth", "qugq", "iwjq", "tdrb", "jxfp", "whmt"}
Returns: 12672
16
{"hldk", "cfdh", "fcef", "fcce", "mldn", "jhlc", "kdbg", "ekck", "nlno", "nnpa", "gkbn", "dodd", "knbk", "fnpp", "dhga", "pkef", "jcbj", "bail", "ggll"}
Returns: 504
5
{"acecd", "addcd", "caedb", "cdaad", "bdcea", "cecda", "adcab", "bbddb", "caaee", "acebe", "cdbcd", "aedce", "caaac", "aebee", "aaeea"}
Returns: 0
13
{"e", "k"}
Returns: 11
21
{"bcj", "tjb", "too", "nkc", "inl"}
Returns: 4352
4
{"ca", "ab", "bb", "aa"}
Returns: 2
14
{"gjlccm", "lllngi", "kheknk", "cbajdn"}
Returns: 1100000
24
{"e", "d", "q"}
Returns: 21
25
{"stn", "rxp", "tsa", "ftr", "sux", "ehd", "ejt", "pup", "otj", "nyo", "tfa", "npp", "xnk", "lrj", "jmm", "bty", "qie", "omd", "yvd", "sbl"}
Returns: 1210
21
{"ai", "lf", "tb", "np", "ke"}
Returns: 256
9
{"bdcd", "edhi", "fcif"}
Returns: 1512
4
{"bc", "bb", "ac", "db", "db", "bd", "ad", "ca", "ca", "bb", "cd", "ac", "ca", "dc", "bc", "cc", "ab", "cd", "ca", "bb", "cc", "ca", "cb", "ac", "bb", "dd", "ad", "ab", "ad", "cb"}
Returns: 0
14
{"kk", "kd", "ib"}
Returns: 132
18
{"ldc", "kog", "dcr"}
Returns: 3375
22
{"phbkjv", "misbci", "oqhqqp", "jknqht", "vuksug"}
Returns: 25557426
19
{"ba", "qi", "jg", "ks", "rk", "qf", "kl"}
Returns: 168
6
{"daaddf", "dceaff", "dfcccf", "bfdace", "dcdcbb", "bcbcab", "fedaca", "fccede", "bddaaf", "bfddbb", "adfdee", "aeaede", "debbbc", "fcbefd", "efcdcc", "eabcba", "bbfffd", "ffacfe", "fffbcf", "acebcc", "bfbaba", "ebefee"}
Returns: 0
20
{"k", "f", "c", "o", "i", "d", "j", "g", "s", "p"}
Returns: 10
20
{"hr", "ht", "ji", "oa", "jg", "an", "fi", "pg", "oa", "lh", "mq", "ff", "ft", "bg", "kt", "mj", "ic", "jh", "br", "pj", "hj", "of", "fr", "jo", "jj"}
Returns: 72
20
{"bct", "tms", "qne", "mmr", "hqr", "nor", "fim", "kkd", "mne", "cnh", "hai", "rak", "mrj", "gic", "bhf", "tll", "cpi", "itl", "gbi", "phd", "qjf", "mis", "gqi", "ffk", "eip", "dji", "emh"}
Returns: 120
8
{"che", "abd", "dbd"}
Returns: 180
16
{"iaklnd", "ckiheh", "pgbfak"}
Returns: 4826809
8
{"hf", "dg"}
Returns: 36
6
{"baddb", "dadee", "adbdb", "fabde", "aecdc"}
Returns: 216
10
{"ad", "dh", "jh", "hg", "ig"}
Returns: 35
5
{"e", "c", "e"}
Returns: 3
24
{"lqmie", "bgbsi", "wiflt", "lhssr", "ehdel", "bexfm", "wviqc", "txreh", "koqxw", "idlia", "uriri", "oqtoe", "levga", "dbmpg", "vvqvs", "fuwlb", "rxfrh", "ppnbw", "pwwwh", "qskqh", "mxoeu", "ffgka", "sqxgr", "ofjqu", "nuprn"}
Returns: 19440
22
{"nmbrb", "btdgp", "grbrd", "akipi", "dvdlp", "aisoo"}
Returns: 1414944
6
{"cda", "dfa", "dfa", "ffb", "cbb", "feb", "bde", "fac", "eff", "fea", "dba", "bfe", "cbc", "cbc", "fec", "bbd", "dec", "fbe", "daa", "dfb", "faa", "baa", "bab", "daa", "edf", "aab", "cff", "bfb", "cbb", "adb"}
Returns: 0
14
{"kl", "ig", "ik"}
Returns: 132
20
{"hli", "gbj", "bfb", "qjj", "nkb", "lti", "fqf", "gta", "roh", "inp", "abk", "tnc", "ctk", "gik", "dte", "tom", "skg", "iio", "hpf", "snm", "gbk", "bhc", "dih", "poe", "tda"}
Returns: 245
19
{"billl", "fcicp", "rqokm"}
Returns: 1048576
6
{"defc"}
Returns: 625
8
{"c", "a", "e", "g", "h", "d", "d", "a", "e", "d", "a", "f", "e", "c", "g", "b", "b", "d", "c", "c", "b", "g", "f", "e", "a", "e"}
Returns: 0
24
{"u", "q", "s", "j", "s", "j", "v", "n", "s", "s", "l", "k", "h", "j", "g", "v", "w"}
Returns: 13
11
{"dcfiah", "cifgbb", "bigick"}
Returns: 373248
6
{"b", "c", "f", "d", "b", "d", "f", "a", "f", "e", "d", "b", "a", "a", "c"}
Returns: 0
18
{"e", "r", "m", "l", "h", "d", "h", "g", "m", "i", "o", "m", "n"}
Returns: 8
16
{"gl", "le", "bb", "ef", "fb", "al"}
Returns: 120
7
{"af", "cf", "cc", "dg", "gf", "gb", "dg", "fd", "bf", "be", "gd", "ab", "bd", "gb", "dc", "aa", "ed"}
Returns: 0
7
{"efg", "cfe"}
Returns: 150
14
{"bjf", "mik", "mdl", "djh", "hnc", "dmk", "ean", "mkb", "gaf", "jka", "hab", "efk", "dfn", "afd", "ddc", "fdg", "nak", "bcm", "jij", "gff", "hhh", "mhj", "cma", "gji", "nih", "ffg", "cik", "iid"}
Returns: 8
16
{"jhp"}
Returns: 3375
8
{"gdha", "fddf", "daga"}
Returns: 900
17
{"klqob", "fdgci", "imadq", "qlnil", "iepee"}
Returns: 292032
10
{"gfijg"}
Returns: 59049
23
{"aijpi", "rvmfg", "mnwuo", "bjpdq", "ujwlq"}
Returns: 2222316
18
{"c", "b", "e", "i", "k", "n", "c", "g", "j", "g", "k", "d", "r", "g", "p", "f", "c", "p", "b", "g", "c", "l", "b", "o", "c", "r", "c", "p"}
Returns: 4
26
{"f", "c", "g", "g", "f", "s"}
Returns: 22
26
{"xrpm", "bzrf", "gyrt", "bvkc", "iqoz", "onhp", "gitq", "fvyz", "mjsz", "tfxs", "fjab", "yrru", "wggs", "cunr", "hraq", "ehwo", "ncqy", "yyqb", "zttz", "fvxm", "jkjm", "pcjj", "jpts", "dxkz", "qkko", "gbta", "axpq", "ovrj", "nkue"}
Returns: 4800
21
{"l", "g", "i", "p", "j", "t", "l", "k", "g", "g", "g", "f", "f", "g", "p", "l", "t", "j", "f", "m", "k", "s"}
Returns: 11
13
{"g", "l", "a", "a", "d", "g", "c", "k", "l", "k", "k", "k", "h", "b", "a", "d", "k", "a", "d", "b", "g", "g", "l", "d", "d", "j", "c"}
Returns: 4
16
{"jc"}
Returns: 225
22
{"jqfe", "vglq", "lice", "rvch", "tjlo"}
Returns: 98838
24
{"otndf", "wxrbe", "ptjtv", "noqnv", "qqnqh", "qifnt", "ddxkm", "ghmwb", "ectfl", "lunjw", "tbonw", "awxrb", "awbtd", "bdrdr", "harej", "qpacq", "trtsi", "pfggk", "wcvts", "pdaov", "oabpo"}
Returns: 60984
7
{"cdcg", "fggb", "gcdg", "fdeb", "cdcg", "decg", "degc", "dabf", "becb", "gacg", "agfd", "caca", "dbge", "cebb", "fgfa", "acbe", "dgec", "addb", "fdac"}
Returns: 0
21
{"ij", "bs", "sj", "hb"}
Returns: 306
10
{"jgeg"}
Returns: 6561
20
{"s", "a", "m", "r", "r", "l", "c", "r", "g", "s", "o", "q", "r", "q", "e", "h", "t", "l", "r", "p", "m", "l"}
Returns: 7
14
{"cd", "hf", "ij", "eg"}
Returns: 100
25
{"fmb", "tyb", "mro", "kbi"}
Returns: 9702
23
{"mh", "la", "dj", "dr"}
Returns: 380
20
{"milm", "lbkn", "fqfn", "aiil", "bsph", "tdjr", "cnpr", "qmlq", "gsog", "mpkh", "mirm", "mdla", "ahib", "doko", "hnsa", "iomk", "flkl", "lhki", "nbgj", "rbtf", "mcip", "dbbe", "jsfp"}
Returns: 1120
17
{"chpknq", "hhjjde", "pcgqmp", "qngiib", "mmjqqf"}
Returns: 4088448
1
{"a", "a", "a"}
Returns: 0
6
{"db", "be", "dd", "ca", "cc", "fd", "da", "ab", "ad", "aa", "ed", "fb", "dc", "df", "cd", "dd", "ae", "de", "bc", "aa", "ed", "af", "fe"}
Returns: 0
26
{"dyetb", "sohko", "lxolc", "vynor", "idwka", "psqqv", "krodv", "gochg", "suify", "pwogo", "kitxq", "fwolh", "bqajf", "pfpjq", "euxru", "uwoww", "lpuyg", "xzcwu", "hnqdw", "hkvab", "qqkdb", "tbokq"}
Returns: 157300
16
{"h", "e"}
Returns: 14
2
{"aaa", "abb", "bbb", "baa", "bbb", "aba", "baa", "baa"}
Returns: 0
23
{"ubgkuw", "flwmkg"}
Returns: 85766121
4
{"ac", "da", "ba"}
Returns: 2
24
{"rft", "luj", "iwm", "aia", "tjn"}
Returns: 6859
5
{"ddd"}
Returns: 64
17
{"lddfkj", "mcdapq"}
Returns: 12150000
16
{"fm", "kf", "mg", "ha", "og"}
Returns: 132
18
{"kcach", "qdpmr", "eljaq", "knpea", "djirq", "cbmcd", "brdjd", "opkgo", "khflb", "dfaci", "ohpjq", "nejkn", "icolf", "lblqg", "baahq", "jidag", "qohhm", "nllqi", "oijif", "jhrqb", "ierqk", "bocac", "jhghd", "ckfqq", "ifinc", "mnjdc"}
Returns: 1152
1
{"aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa"}
Returns: 0
20
{"sjkt", "lqsb", "ppjc", "ofgi", "bqql"}
Returns: 54000
12
{"d", "f"}
Returns: 10
25
{"fmnr", "phjd", "fkdo", "iewi", "itxy", "dnkf", "chef", "xhbq", "yaks", "ybec", "iaub", "laxs", "ijaf", "oghk", "myjy", "dydc", "oafj", "fcvs", "rkcw"}
Returns: 24024
16
{"ikjb", "amkg"}
Returns: 38416
19
{"dnpfd", "cdrso", "laqis", "rqrfp", "aochi", "dlkjo"}
Returns: 499408
17
{"ba", "pn", "ca", "fn", "jb", "ii", "bi", "dd", "qi", "of", "ff", "oc", "qb", "ql", "mb", "dm"}
Returns: 56
10
{"befcjb", "fecjha", "ggghig"}
Returns: 134456
16
{"bnga", "moji", "lfcj", "djnb", "pdnb", "afgd", "fmdk", "ahgp", "fpfi", "bbff", "fgfp", "engh", "ehie", "eglo", "bdkj", "bcol", "gogg"}
Returns: 630
22
{"qsd", "tkg", "jjt", "cak", "mae", "nvf", "col", "dqt", "tih", "lat", "vfk", "qqn", "sfa", "gbp", "epu", "uct", "ast"}
Returns: 800
2
{"aba", "aba", "bab", "bab", "baa", "bab", "bab", "aab", "abb", "aba", "baa", "bba", "baa", "aaa", "bba"}
Returns: 0
1
{"aaa", "aaa", "aaa", "aaa"}
Returns: 0
19
{"bkmpcn", "isckfn", "dsqcoe", "msrlna", "pnfgnl"}
Returns: 9878400
1
{"aaaaaa" }
Returns: 0
7
{"baba", "babe", "cage", "cafe", "feed", "deed", "deaf", "dead" }
Returns: 90
1
{"aaaaa", "aaaaa" }
Returns: 0
26
{"aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa", "aaaaaa" }
Returns: 244140625
2
{"aaa", "aba" }
Returns: 0
3
{"abacaa", "abacaa", "acabab" }
Returns: 8