Coding Quiz: Good Palindrome Partition

The problem is Luogu B4520. Given a lowercase string S, split it into the minimum number of good strings.

A good string is a palindrome, and its left half is non-decreasing. The right half is then forced by the palindrome constraint.

Examples from the statement:

z          good
bbb        good
accgcca    good
ccdeeedcc  good
ghg        good

acbca      not good
syzzh      not good
ccb        not good

Minimum partition examples:

accgcca -> accgcca -> 1
czccc   -> czc | cc -> 2
ababa   -> a | b | aba -> 3
ccb     -> cc | b -> 2

§Haskell checker

The Haskell implementation is the executable spec. It generates every possible partition, keeps the partitions whose pieces match the definition, then takes the minimum number of pieces.

import Control.Applicative (liftA2)
import Control.Category ((>>>))
import System.IO (BufferMode (LineBuffering), hSetBuffering, stdout)

all_partitions :: String -> [String]
all_partitions "" = [""]
all_partitions [e] = [[e]]
all_partitions (e : es) = [e : sep ++ rest | sep <- ["", " "], rest <- all_partitions es]

is_palindrome :: String -> Bool
is_palindrome s = s == reverse s

is_eq_or_growing :: String -> Bool
is_eq_or_growing [] = True
is_eq_or_growing [x] = True
is_eq_or_growing (x : y : rest) = x <= y && is_eq_or_growing (y : rest)

is_good_palindrome = liftA2 (&&) is_palindrome (first_half >>> is_eq_or_growing)
  where
    first_half str = take ((length str + 1) `div` 2) str

num_good_palindrome_partitions :: String -> Int
num_good_palindrome_partitions =
  all_partitions
    >>> map words
    >>> filter (all is_good_palindrome)
    >>> map length
    >>> minimum

main = do
  hSetBuffering stdout LineBuffering
  interact $ lines >>> map (num_good_palindrome_partitions >>> show) >>> unlines

§Java implementation

The Java naive implementation follows the same brute-force pipeline as the Haskell checker: generate all partition candidates, filter partitions whose pieces are good, then take the minimum number of pieces. The difference is in candidate generation. Java generates candidates with DFS by carrying one trace and branching at each character. The Haskell version expresses candidate generation in a BFS-style approach.

The optimized implementation is a linear DP. num_partitions[i] is the answer for prefix s[0, i). The key idea is to use run-length encoding (RLE) blocks.

import java.io.*;
import java.nio.charset.*;
import java.nio.file.*;
import java.util.*;

class split_palindrome {
    static final Path HASKELL_SCRIPT = Path.of("good_palindrome.hs");
    static HaskellNaiveChecker haskell_checker;

    static final class HaskellNaiveChecker implements AutoCloseable {
        final Process process;
        final BufferedWriter stdin;
        final BufferedReader stdout;

        HaskellNaiveChecker(Path script) {
            try {
                process = new ProcessBuilder("runghc", script.toString())
                        .redirectError(ProcessBuilder.Redirect.INHERIT)
                        .start();
                stdin = process.outputWriter(StandardCharsets.UTF_8);
                stdout = process.inputReader(StandardCharsets.UTF_8);
            } catch (IOException e) {
                throw new AssertionError("Failed to start Haskell naive checker: " + script, e);
            }
        }

        int num_partitions(String input) {
            try {
                stdin.write(input);
                stdin.newLine();
                stdin.flush();

                String line = stdout.readLine();
                if (line == null) {
                    throw new AssertionError("Haskell naive checker ended early for input \"" + input + "\"");
                }

                try {
                    return Integer.parseInt(line.trim());
                } catch (NumberFormatException e) {
                    throw new AssertionError(
                            "Haskell naive checker returned a non-integer for input \"" + input + "\": " + line,
                            e);
                }
            } catch (IOException e) {
                throw new AssertionError("Failed to interact with Haskell naive checker for input \"" + input + "\"",
                        e);
            }
        }

        @Override
        public void close() {
            try {
                stdin.close();
                int exit_code = process.waitFor();
                stdout.close();
                if (exit_code != 0) {
                    throw new AssertionError("Haskell naive checker exited with code " + exit_code);
                }
            } catch (IOException e) {
                throw new AssertionError("Failed to close Haskell naive checker", e);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                throw new AssertionError("Interrupted while closing Haskell naive checker", e);
            }
        }
    }

    static int num_good_palindrome_partitions(char[] s) {
        final int n = s.length;
        if (n <= 1) {
            return n;
        }

        // run-length-encoding
        // block-start := block-idx -> block-start-idx
        // block-len := num of elems in this block
        int[] block_start = new int[n];
        int[] block_len = new int[n];
        Arrays.fill(block_start, -1);
        int num_blocks = 0;

        // num_partitions := prefix_len -> result
        int[] num_partitions = new int[n + 1];

        // min num of partition for suffix of taking 0, 1, ... max from current block
        int cur_min_num_partition = 0;

        int num_blocks_after_peak = 0;

        for (int i = 0; i < n; i++) {
            final int prefix_len = i + 1;
            if (i > 0 && s[i - 1] == s[i]) {
                // same block
                block_len[num_blocks - 1]++;
                cur_min_num_partition = Math.min(cur_min_num_partition, num_partitions[i]);
            } else {
                // new block
                num_blocks++;
                block_start[num_blocks - 1] = i;
                block_len[num_blocks - 1] = 1;
                cur_min_num_partition = num_partitions[i];

                if (i == 0 || s[i - 1] < s[i]) {
                    num_blocks_after_peak = 0;
                } else {
                    num_blocks_after_peak++;
                    int completed_right_block = num_blocks - 2;
                    int mirrored_left_block = completed_right_block - 2 * (num_blocks_after_peak - 1);
                    if (mirrored_left_block < 0
                            || s[block_start[mirrored_left_block]] != s[block_start[completed_right_block]]
                            || block_len[mirrored_left_block] != block_len[completed_right_block]) {
                        num_blocks_after_peak = 0;
                    }
                }
            }

            num_partitions[prefix_len] = cur_min_num_partition + 1;

            int right_block = num_blocks - 1;
            if (num_blocks_after_peak != 0) {
                int left_block = right_block - (2 * num_blocks_after_peak);
                if (left_block >= 0
                        && s[block_start[left_block]] == s[block_start[right_block]]
                        && block_len[left_block] >= block_len[right_block]) {
                    int prev_prefix_len = block_start[left_block] + block_len[left_block] - block_len[right_block];
                    num_partitions[prefix_len] = Math.min(num_partitions[prefix_len],
                            num_partitions[prev_prefix_len] + 1);
                }
            }
        }

        // Last elem
        return num_partitions[n];
    }

    static boolean is_good_palindrome(char[] s) {
        if (s.length <= 1) {
            return true;
        }
        for (int i = 0; i < s.length / 2; i++) {
            if (i + 1 < s.length && s[i] > s[i + 1]) {
                return false;
            }
            if (s[i] != s[s.length - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    static void dfs_inner(char[] s, int start, ArrayList<String> trace, ArrayList<String[]> acc) {
        if (start == s.length) {
            // edge/base case
            acc.add(trace.toArray(String[]::new));
            return;
        }

        char e = s[start];
        // branching
        trace.add(e + "");
        dfs_inner(s, start + 1, trace, acc);
        trace.removeLast();

        if (!trace.isEmpty()) {
            var new_last = trace.getLast() + e;
            trace.removeLast();
            trace.addLast(new_last);
            dfs_inner(s, start + 1, trace, acc);
        }
    }

    static ArrayList<String[]> all_substr(char[] s) {
        ArrayList<String[]> result = new ArrayList<>();

        dfs_inner(s, 0, new ArrayList<>(), result);

        return result;
    }

    static int naive_count(char[] s) {
        String input = new String(s);
        var strs = all_substr(s);
        int num_java_partitions = strs.stream()
                .filter(it -> Arrays.stream(it).allMatch(
                        str -> is_good_palindrome(str.toCharArray())))
                .map(it -> it.length)
                .min(Integer::compare)
                .orElse(0);

        if (haskell_checker == null) {
            throw new AssertionError("Haskell naive checker has not been started");
        }
        int num_haskell_partitions = haskell_checker.num_partitions(input);
        if (num_java_partitions != num_haskell_partitions) {
            throw new AssertionError(
                    "Haskell naive check failed for input \"" + input + "\": java="
                            + num_java_partitions + ", haskell=" + num_haskell_partitions);
        }

        return num_java_partitions;
    }

    static int num_partitions_checked(String s, String context) {
        int num_partitions = num_good_palindrome_partitions(s.toCharArray());
        int num_naive_partitions = naive_count(s.toCharArray());
        if (num_partitions != num_naive_partitions) {
            throw new AssertionError(
                    context + " mismatch for input \"" + s + "\": linear=" + num_partitions
                            + ", naive=" + num_naive_partitions);
        }
        return num_partitions;
    }

    /**
     * Generates a completely arbitrary lowercase ASCII string with length in [0,
     * max_len].
     * This is the broad fuzzing case: it does not try to create palindromes or
     * valid
     * partitions. It is useful for catching general disagreements between the naive
     * and
     * dynamic-programming implementations, especially around empty strings, single
     * chars,
     * and strings that should mostly split into small pieces.
     */
    static String random_input(Random random, int max_len) {
        int len = random.nextInt(max_len + 1);
        char[] s = new char[len];
        for (int i = 0; i < len; i++) {
            s[i] = (char) ('a' + random.nextInt(26));
        }
        return new String(s);
    }

    /**
     * Returns a random lowercase ASCII character different from c.
     * This is used when deliberately breaking a palindrome: changing one mirrored
     * character to a different value guarantees that the string is no longer a
     * palindrome
     * at that position.
     */
    static char random_different_lowercase(Random random, char c) {
        return (char) ('a' + (c - 'a' + 1 + random.nextInt(25)) % 26);
    }

    /**
     * Generates one valid "good palindrome" with exactly len characters.
     * A good palindrome must satisfy both rules checked by the two implementations:
     * it must read the same forward and backward, and its characters must not
     * decrease
     * while moving from the left edge toward the center. The method first generates
     * that
     * nondecreasing left side, then mirrors it to fill the right side.
     */
    static String random_good_palindrome_of_len(Random random, int len) {
        char[] s = new char[len];
        char prev = 'a';
        for (int i = 0; i < (len + 1) / 2; i++) {
            char c = (char) (prev + random.nextInt('z' - prev + 1));
            s[i] = c;
            prev = c;
        }
        for (int i = 0; i < len / 2; i++) {
            s[len - 1 - i] = s[i];
        }
        return new String(s);
    }

    /**
     * Generates one valid good palindrome with length in [0, max_len].
     * This wraps random_good_palindrome_of_len when the exact length is not
     * important.
     * These cases make sure the test harness frequently exercises the successful
     * path,
     * because normal random strings almost never contain long good palindromes.
     */
    static String random_good_palindrome(Random random, int max_len) {
        return random_good_palindrome_of_len(random, random.nextInt(max_len + 1));
    }

    /**
     * Generates a string close to being a good palindrome, but usually invalid.
     * The method starts with a valid good palindrome and then breaks one of the
     * required
     * properties. Sometimes it keeps the mirror structure but forces a decreasing
     * step
     * near the left edge. Other times it changes one mirrored character so the
     * string is
     * no longer a palindrome. These near-misses are useful because they exercise
     * boundary
     * cases where an implementation might accept too much.
     */
    static String random_near_good_palindrome(Random random, int max_len) {
        int len = random.nextInt(max_len + 1);
        char[] s = random_good_palindrome_of_len(random, len).toCharArray();
        if (len < 2) {
            return new String(s);
        }

        if (len >= 3 && random.nextBoolean()) {
            s[0] = 'z';
            s[1] = 'a';
            s[len - 1] = 'z';
            s[len - 2] = 'a';
        } else {
            int i = random.nextInt(len / 2);
            s[len - 1 - i] = random_different_lowercase(random, s[len - 1 - i]);
        }
        return new String(s);
    }

    /**
     * Generates a string by concatenating several valid good palindromes.
     * This targets the partitioning part of the problem instead of only checking
     * whether
     * the whole string is good. Since the complete string may not be one good
     * palindrome,
     * the dynamic-programming implementation has to find the same split points that
     * the
     * naive exhaustive implementation finds.
     */
    static String random_partitioned_input(Random random, int max_len) {
        int len = random.nextInt(max_len + 1);
        if (len == 0) {
            return "";
        }

        int num_parts = 1 + random.nextInt(Math.min(4, len));
        int num_remaining_chars = len;
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < num_parts; i++) {
            int num_remaining_parts = num_parts - i - 1;
            int part_len = 1 + random.nextInt(num_remaining_chars - num_remaining_parts);
            result.append(random_good_palindrome_of_len(random, part_len));
            num_remaining_chars -= part_len;
        }
        return result.toString();
    }

    static void run_randomized_tests(int num_cases, int max_len) {
        Random random = new Random();
        for (int i = 0; i < num_cases; i++) {
            String kind;
            String s;
            switch (i % 4) {
                case 0 -> {
                    kind = "uniform";
                    s = random_input(random, max_len);
                }
                case 1 -> {
                    kind = "good palindrome";
                    s = random_good_palindrome(random, max_len);
                }
                case 2 -> {
                    kind = "near good palindrome";
                    s = random_near_good_palindrome(random, max_len);
                }
                default -> {
                    kind = "partitioned good palindromes";
                    s = random_partitioned_input(random, max_len);
                }
            }
            num_partitions_checked(s, "randomized " + kind + " check at case " + i);
        }
        System.out.println("Randomized check passed: " + num_cases + " cases");
    }

    /**
     * Runs exhaustive comparison tests over every string in a small search space.
     * For each length up to max_len, this enumerates every string that can be built
     * from
     * the supplied alphabet. This complements the randomized tests: it is limited
     * to a
     * small alphabet so it stays fast, but it guarantees complete coverage of all
     * short
     * inputs in that space.
     */
    static void run_exhaustive_tests(int max_len, String alphabet) {
        int num_cases = 0;
        for (int len = 0; len <= max_len; len++) {
            int num_combinations = 1;
            for (int i = 0; i < len; i++) {
                num_combinations *= alphabet.length();
            }

            for (int mask = 0; mask < num_combinations; mask++) {
                int x = mask;
                char[] chars = new char[len];
                for (int i = 0; i < len; i++) {
                    chars[i] = alphabet.charAt(x % alphabet.length());
                    x /= alphabet.length();
                }

                String s = new String(chars);
                num_partitions_checked(s, "exhaustive check");
                num_cases++;
            }
        }
        System.out.println("Exhaustive check passed: " + num_cases + " cases");
    }

    public static void main(String[] args) {
        final int num_random_cases = 1_000;
        final int random_max_len = 12;
        final int exhaustive_max_len = 8;
        final String exhaustive_alphabet = "abc";

        try (var checker = new HaskellNaiveChecker(HASKELL_SCRIPT)) {
            haskell_checker = checker;

            String[] inputs = {
                    "czccc",
                    "ababa",
                    "edffd",
                    "bbdddbb",
                    "aaababa"
            };
            for (var s : inputs) {
                System.out.println(s + " result: " + num_partitions_checked(s, "fixed check"));
            }

            run_randomized_tests(num_random_cases, random_max_len);
            run_exhaustive_tests(exhaustive_max_len, exhaustive_alphabet);
        } finally {
            haskell_checker = null;
        }
    }
}