UVA - 11022 - String Factoring

This article will explain my thought process to solve a problem called String Factoring (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Dynamic Programming, Sliding Window

Objective

Given:

A string.

We want to:

Find the minimum weight after the string factorization.

Glossary

Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Sliding Window — A technique for processing contiguous segments of data by moving a fixed-size or variable-size window across a sequence.

Observation

We can do factorization to condense the string by identifying a consecutive identical substring. For example ABBAB can be condensed into A (B)^2 AB. Since the length of the string is quiet small, it is possible to iteratively explore every possible substring using sliding window technique. For example, the substrings of ABBAB are:

From 0th letter: A, AB, ABB, ABBA, ABBAB
From 1st letter: B, BB, BBA, BBAB
From 2nd letter: B, BA, BAB
From 3rd letter: A, AB
From 4th letter: B

After the substrings are identified, we want to try to identify the consecutive identical substring. For each substring, we want to iteratively multiply the substring and check whether the string contains the multiplied substring. For example, if the substring is BA, then we want to check BABA, BABABA, BABABABA, etc.

After the consecutive identical substring is identified, we want to split the string into 3 parts: prefix, factor, and suffix. For example if the string is ABBAB, the substring is B, and the consecutive identical substring is BB, then the prefix is A, the factor is B, and the suffix is AB.

After the prefix, factor, and suffix are identified, since it is still possible for each parts to contains consecutive identical substring, we could recursively apply the same factorization mechanism to the prefix, factor, and suffix, until there is no consecutive identical substring.

If there is no identical substring, then the weight is equals to the length of the string. If there is an identical substring, then the weight is equals to the sum of weight of the prefix, factor, and suffix. Since we want to minimize the weight, we must choose the minimum weight out of every possible factor.

At this point, we should have known the minimum weight of the string. To further optimize the process, we can use DP strategy to avoid recomputation by storing the minimum weight of every computed string.

Algorithm

The sliding window to generate the substrings can be implemented using nested loop. The first loop will point to the start of the substring, and the second loop will point to the end of the substring. After that, we iteratively check whether the next substring is identical or not to form the consecutive identical substring. This will let us split the string into 3 parts: prefix, factor, and suffix.

Since the process of splitting the string into prefix, factor, and suffix is being done in a recursive manner, the DP will naturally being implemented with top-down approach. The string will be the state of the DP and the minimum weight will be the value of the DP.

The time complexity of this solution is O({string length}^4) or O(10^7).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.*;

/**
 * 11022 - String Factoring
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1963
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNext()) {
            final Input input = new Input();
            input.string = in.next();
            if (input.isEOF()) break;

            final Output output = process.process(input);
            out.println(output.weight);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public String string;

    public boolean isEOF() {
        return "*".equals(string);
    }
}

class Output {
    public int weight;
}

class Process {
    private final Map<String, Integer> weightPerString = new HashMap<>();

    public Output process(final Input input) {
        final Output output = new Output();
        output.weight = getWeight(input.string);
        return output;
    }

    private int getWeight(final String string) {
        if (weightPerString.containsKey(string)) {
            return weightPerString.get(string);
        }

        int minWeight = string.length();
        for (int i = 0; i < string.length(); i++) {
            for (int length = 1; length < string.length() - i; length++) {
                final int start1 = i, end1 = i + length;
                final String factor1 = string.substring(start1, end1);

                for (int j = i + length; j < string.length(); j += length) {
                    final int start2 = j, end2 = Math.min(j + length, string.length());
                    final String factor2 = string.substring(start2, end2);

                    final boolean repeatable = factor1.equals(factor2);
                    if (!repeatable) break;

                    final String prefix = string.substring(0, start1);
                    final String suffix = string.substring(end2, string.length());

                    final int weight = getWeight(prefix) + getWeight(factor1) + getWeight(suffix);
                    minWeight = Math.min(minWeight, weight);
                }
            }
        }

        weightPerString.put(string, minWeight);
        return minWeight;
    }
}