Statistics

Problem Statement for "NextBetter"

Problem Statement

String matching is extraordinarily useful. In our application, we define the match quality between 2 strings of lowercase letters to be the number of positions that match exactly. For example, the match quality between "abcdedd" and "bcddd" is 1, since they only match in the 4th character.

We have a string sequence, data, and are interested in finding string sequences of the same length that fit the data well. We say that one sequence fits the data better than another sequence if it has a higher quality match with the data at the first position where the match qualities differ.

String sequences are ordered lexicographically based on the normal alphabetical comparison between individual strings. That means that if position i is the first position where 2 sequences differ, the sequence whose ith element would come later in a dictionary is later in the ordering of sequences. Given data and candidate return the next later permutation of candidate that fits data better. If no lexicographically later permutation of candidate gives a better fit, return candidate.

Definition

Class:
NextBetter
Method:
nextPerm
Parameters:
String[], String[]
Returns:
String[]
Method signature:
String[] nextPerm(String[] data, String[] candidate)
(be sure your method is public)

Constraints

  • data will contain between 1 and 50 elements, inclusive.
  • candidate will contain the same number of elements as data.
  • Each element of data and candidate will contain between 1 and 10 characters, inclusive.
  • Each element of data and candidate will contain only lowercase letters ('a'-'z').

Examples

  1. {"ab","cde"}

    {"xx","ade"}

    Returns: {"xx", "ade" }

    The only permutation of "xx","ade" is earlier (since "ade" precedes "xx"). Therefore, there is no next permutation, and candidate is returned.

  2. {"ad","cde"}

    {"xx","yde"}

    Returns: {"yde", "xx" }

    "yde","xx" is the next permutation of "xx","yde" and it fits data better since it has a match quality of 1 in the first position ("yde" vs "ad") while candidate has a match quality of 0 in the first position of data.

  3. {"ade","cde","acd"}

    {"ab","ae","c"}

    Returns: {"ab", "c", "ae" }

    All 5 permutations of candidate come later than candidate. "ab","c","ae" fits data better than candidate, and so does "ae","c","ab". None of the other permutations fits data better than candidate. So the return is the earlier of these 2.

  4. {"k","k","s","k"}

    {"a","y","y","s"}

    Returns: {"y", "a", "s", "y" }

    //String[] t={"k","k","s","k"}, s={"a","y","y","s"}; //return "y","a","s","y"

  5. {"k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k", "kza","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","s","k","k","k","k","k","k","k"}

    {"a","yz","yy","yx","yk","yj","yi","yh","yg","yf","ye","yd","yc","yb","ya","ty","tty","ttty","yyn","yym","yyl","yyk","yyj","yyi","yyh","yyg","yyf","yye","yyd","yyc","yyb","yya","yvq","yvp","yvo","yvn","yvm","yvl","yvk","yvj","yvi","yvh","yvg","yvf","yve","yvd","yvc","yvb","yva","s"}

    Returns: {"a", "yz", "yy", "yx", "yk", "yj", "yi", "yh", "yg", "yf", "ye", "yd", "yc", "yb", "ya", "ty", "tty", "yva", "s", "ttty", "yvb", "yvc", "yvd", "yve", "yvf", "yya", "yvg", "yvh", "yvi", "yvj", "yvk", "yvl", "yvm", "yvn", "yvo", "yvp", "yvq", "yyb", "yyc", "yyd", "yye", "yyf", "yyg", "yyh", "yyi", "yyj", "yyk", "yyl", "yym", "yyn" }

  6. {"k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k", "kza","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","k","s","k","k","k","k","k","k","k"}

    {"aaa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao","ap","aq","ar","as","at","au","av","aw","ax","ay","ba","bb","bc","bd","be","bf","bg","bh","bi","bj","bk","bl","bm","bn","bo","bp","bq","br","bs","bt","bu","bv","bw","bx","by"}

    Returns: {"ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak", "al", "am", "an", "ao", "ap", "aq", "ar", "as", "at", "au", "av", "aw", "ax", "ay", "ba", "aaa", "bb", "bc", "bd", "be", "bf", "bg", "bh", "bi", "bj", "bk", "bl", "bm", "bn", "bo", "bp", "bq", "br", "bs", "bt", "bu", "bv", "bw", "bx", "by" }

  7. {"abc"}

    {"abb"}

    Returns: {"abb" }

  8. { "acbc", "acab", "abbc"}

    { "bcb", "aac", "cab"}

    Returns: {"bcb", "aac", "cab" }

  9. { "facdd", "bbbca", "acbba", "fcaef"}

    { "dcdb", "effe", "acaf", "fdaa"}

    Returns: {"fdaa", "acaf", "dcdb", "effe" }

  10. { "ba", "dc", "de", "de", "ad", "ce", "bb", "cc", "ae", "ce"}

    { "eaee", "dbdc", "ccec", "ecab", "ccdc", "cecd", "edca", "bbaa", "beda", "bdac"}

    Returns: {"eaee", "dbdc", "ccec", "ecab", "edca", "bbaa", "bdac", "beda", "ccdc", "cecd" }

  11. {"cc", "ae", "ce"}

    {"bbaa", "beda", "bdac"}

    Returns: {"bbaa", "beda", "bdac" }

  12. {"zy", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "za", "zb", "zc", "zd", "ze", "zf", "zg", "zh", "zi", "zj", "zk", "zl", "zm", "zn", "zo", "zp", "zq", "zr", "zs", "zt", "zu", "zv", "zw", "zx"}

    {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "za", "zb", "zc", "zd", "ze", "zf", "zg", "zh", "zi", "zj", "zk", "zl", "zm", "zn", "zo", "zp", "zq", "zr", "zs", "zt", "zu", "zv", "zw", "zx", "zy"}

    Returns: {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "za", "zb", "zc", "zd", "ze", "zf", "zg", "zh", "zi", "zj", "zk", "zl", "zm", "zn", "zo", "zp", "zq", "zr", "zs", "zt", "zu", "zv", "zw", "zy", "zx" }

  13. {"zy", "zx", "zw", "zv", "zu", "zt", "zs", "zr", "zq", "zp", "zo", "zn", "zm", "zl", "zk", "zj", "zi", "zh", "zg", "zf", "ze", "zd", "zc", "zb", "za", "y", "x", "w", "v", "u", "t", "s", "r", "q", "p", "o", "n", "m", "l", "k", "j", "i", "h", "g", "f", "e", "d", "c", "b", "a"}

    {"z", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "za", "zb", "zc", "zd", "ze", "zf", "zg", "zh", "zi", "zj", "zk", "zl", "zm", "zn", "zo", "zp", "zq", "zr", "zs", "zt", "zu", "zv", "zw", "zx", "zy"}

    Returns: {"z", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "za", "y", "zb", "zc", "zd", "ze", "zf", "zg", "zh", "zi", "zj", "zk", "zl", "zm", "zn", "zo", "zp", "zq", "zr", "zs", "zt", "zu", "zv", "zw", "zx", "zy" }

  14. {"aa", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "az"}

    {"ab", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "az", "za"}

    Returns: {"za", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "ab", "az" }

  15. {"xrm","xxm","x","xp","xrf","x","ttt"}

    {"amm","bpm","cp","dp","er","fpt","gff"}

    Returns: {"amm", "bpm", "cp", "dp", "er", "gff", "fpt" }

  16. {"xrm","xxm","x","xp","xrf","x","ttt"}

    {"gff","fpt","er","dp","cp","bpm","amm"}

    Returns: {"gff", "fpt", "er", "dp", "cp", "bpm", "amm" }

  17. {"xrr","xxm","x","xp","xrf","x","ttm"}

    {"aff","fpt","er","dp","cp","bpm","amm"}

    Returns: {"amm", "aff", "bpm", "cp", "er", "dp", "fpt" }

  18. {"q","xrr","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","q","xxm","x","xp","xrf","x","ttm"}

    {"g","afrf","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","g","fpt","er","dp","cp","bpm","amm"}

    Returns: {"g", "er", "afrf", "amm", "cp", "dp", "fpt", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "g", "bpm", "g", "g", "g", "g", "g" }

  19. { "aabc", "cbca", "cbcb", "cbac", "aabc", "bccc", "babb"}

    { "bb", "aa", "ac", "cb", "cb", "bc", "cc"}

    Returns: {"bb", "aa", "bc", "cb", "ac", "cb", "cc" }

  20. { "f", "a", "e", "a", "a", "f", "f", "f", "e"}

    { "e", "a", "b", "a", "d", "c", "f", "a", "e"}

    Returns: {"e", "a", "b", "a", "d", "f", "a", "c", "e" }

  21. {"qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p","p"}

    {"b" ,"uqrl" ,"xqrl" ,"wqrl" ,"vqll" ,"aq" ,"tqlll","sqrl","zz","z","zzz"}

    Returns: {"b", "wqrl", "aq", "sqrl", "vqll", "uqrl", "xqrl", "tqlll", "z", "zz", "zzz" }

  22. {"pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p","p"}

    {"pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p", "b" ,"uqrl" ,"xqrl" ,"wqrl" ,"vqll" ,"aq" ,"tqlll","sqrl","zz","z","zzz"}

    Returns: {"pq", "pq", "pq", "pql", "pq", "pqpl", "pqppl", "p", "p", "qqqqq", "pq", "pq", "pq", "pql", "pq", "pqpl", "pqppl", "p", "p", "qqqqq", "pq", "pq", "pq", "pql", "pq", "pqpl", "pqppl", "p", "p", "qqqqq", "pq", "pq", "pq", "pql", "pq", "pqpl", "pqppl", "p", "p", "b", "wqrl", "aq", "sqrl", "vqll", "uqrl", "xqrl", "tqlll", "z", "zz", "zzz" }

  23. {"qqqqq","pq" ,"pq" ,"pq" ,"pql" ,"pq" ,"pqpl" ,"pqppl","p","p","p", "pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","p","pqppl","p","pqppl","p","pqppl","p","pqppl","p","pqppl"}

    {"b" ,"uqrl" ,"xqrl" ,"wqrl" ,"vqll" ,"aq" ,"tqlll","sqrl","zz","z","zzz", "zz","z","zzz","zz","z","zzz","zz","z","zzzq","zz","z","zzzr","zz","z","zzz","zz","z","zzzrrr","zzv","z", "zzzs","zz","z","zzz","zz","z","zzzm","zz","z","zzz"}

    Returns: {"b", "wqrl", "aq", "sqrl", "vqll", "uqrl", "xqrl", "tqlll", "z", "z", "z", "z", "z", "z", "z", "z", "z", "z", "z", "zz", "zz", "zz", "zz", "zz", "zz", "zz", "zz", "zz", "zz", "zzv", "zzz", "zzz", "zzz", "zzz", "zzz", "zzz", "zzzm", "zzzq", "zzzr", "zzzrrr", "zzzs" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: