Hackerrank_MaximumPermutation [source code]

import java.io.*;

public class Hackerrank_MaximumPermutation {
static
/******************************************************************************/
public class Solution {
    static boolean DEBUG = true;

    static String maximumPermutation(String w, String s) {
        Map<String, Integer> substrings = new HashMap<> ();
        Integer[] counts = new Integer[256];
        for (int i = 0; i < w.length (); i++) { 
            char c = w.charAt (i);
            if (counts[c] == null)
                counts[c] = 0;
            counts[c]++;
        }
        int i = 0, j = 0, total = w.length ();
        while (j < s.length ()) {
            // window is still i..j-1
            char peek = s.charAt (j);
            if (counts[peek] == null) {
                while (i < j)
                    counts[s.charAt (i++)]++;
                j++;
                i = j;
                total = w.length ();
                continue;
            }
            while (counts[peek] == 0) {
                counts[s.charAt (i++)]++;
                total++;
            }
            counts[peek]--;
            total--;
            if (total == 0) {
                String substring = s.substring (i, i + w.length ());
                substrings.put (substring, substrings.getOrDefault (substring, 0) + 1);
                total++;
                counts[s.charAt (i++)]++;
            }
            j++;
        }
        if (substrings.isEmpty ())
            return "-1";
        int max_count = -1;
        String max_substr = "";
        for (String substr : substrings.keySet ()) {
            Integer cur_count = substrings.get (substr);
            if (cur_count > max_count || cur_count == max_count && substr.compareTo (max_substr) < 0) {
                max_count = cur_count;
                max_substr = substr;
            }
        }
        return max_count > 0 ? max_substr : "-1";
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        Hackerrank_MaximumPermutation.Solution tester = new Hackerrank_MaximumPermutation.Solution();
        String[] inputs = {
            "aab", "aababaa", "aba",
            "xabd", "absdasfsatsads", "-1",
            "BECO", "ADOBECODEBANC", "BECO",
            "ADOBE", "ADOBECODEBANCADOBECODEBANC", "ADOBE",
            "CODEB", "ADOBECODEBANCADOBECODEBANC", "BECOD",
            "EBANC", "ADOBECODEBANC", "EBANC",
            "ab", "aaaaaaaaaab", "ab",
            "a", "aaaaaaaaaa", "a",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println (Printer.separator ());
            String w = inputs[3 * i].toLowerCase (), s = inputs[3 * i + 1].toLowerCase (), ans = inputs[3 * i + 2].toLowerCase (), output = tester.maximumPermutation (w, s);
            System.out.printf ("%s and %s -> %s, expected: %s\n", 
                w, s, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
            );
        }

        System.out.println (Printer.separator ());
        System.out.println ("Starting real file tests");
        runRealTests (tester);
    }

    static void runRealTests (Hackerrank_MaximumPermutation.Solution tester) {
        String file_path = "hackerrank/maximum-permutation/";
        for (int iter = 40; iter < 100; iter++) {
            String input_file_name = file_path + "input/" + "input" + iter + ".txt", output_file_name = file_path + "output/" + "output" + iter + ".txt";
            Scanner input_scan = null;
            try {
                input_scan = new Scanner (new File (input_file_name));
            } catch (Exception e) {
                continue;
            }
            Scanner output_scan = null;
            try {
                output_scan = new Scanner (new File (output_file_name));
            } catch (Exception e) {
                System.out.printf ("Missing output file for TEST CASE %d\n", iter);
                continue;
            }
            System.out.printf ("TEST CASE #%d\n", iter);
            String line = input_scan.nextLine();
            Integer t = -1;
            try {
                t = Integer.parseInt(line.trim());
            } catch (Exception e) {
                System.out.printf ("Error parsing int from:\n%s\n", line);
                e.printStackTrace ();
            }

            for (int t_i = 0; t_i < t; t_i++) {
                String w = input_scan.nextLine();
                String s = input_scan.nextLine();
                System.out.printf ("enter test item %d\n", t_i);
                String result = tester.maximumPermutation(w, s);
                System.out.printf ("exit test item %d\n", t_i);
                String ans = output_scan.nextLine ();
                System.out.printf ("Result for TEST CASE %d item %d: %s\n\n", iter, t_i, result.equals (ans) ? Printer.wrap ("success", 92) : Printer.wrap ("fail", 91));
            }
        }
    }
}

    while (i < j && counts[peek] == 0) {  
        counts[chs[i++]]++;  
        total++;  
        if (i == j) {  
            i++;  
            j++;  
            continue search;  
        }  
    }

最后死活是过不了一些case, 后面有空等contest结束再来看看到底是什么问题好了; 感觉hackerrank的这个OJ有问题; 这里非要加这个对最后的Map的Empty的判断, 不然foreach好像会报错, 但是我本地试了根本没有这个问题;

自己写的这个test, 就全过; 这个OJ真的是无语了;

38好像直接爆heap了, 不知道是什么原因; 看来这个substring不能乱用? 那怎么办?

Problem Description

https://www.hackerrank.com/contests/university-codesprint-4/challenges/maximum-permutation/problem