Kattis "Chasing Subs" custom decryption challenge

Question

I wrote a function to solve a problem in Java, but it's still too brute force, and I'd like to optimize in terms of runtime.

Link to the description of the problem. The input consists of two lines: a fragment of plaintext, preceded by the message that is encrypted using some unknown character-to-character mapping. The challenge is to find out where the plaintext fragment could have come from.

What I have tried in the code below is to go over the encrypted string char by char (for the length of my key every time), and try to make a dictionary. If I could successfully assign every character from the key to a character from the encrypted text in a deterministic manner, then I note it down in a counter, and start over from the next character in the encrypted text.

So far this solution works on every test, until it reaches huge test case where my "brute force" solution is exceeding the time limit.

Any ideas on how could I improve performance or try a different approach?

package chasingsubs;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class ChasingSubs {

    private void decrypt(String line, String key) {
        int counter = 0;
        int startIndex = 0;
        for (int i = 0; i < line.length() - key.length() + 1; i++) {
            HashMap<Character, Character> dictionary = new HashMap<>();
            HashSet<Character> used = new HashSet<>();

            for (int j = 0; j < key.length(); j++) {
                Character keyChar = key.charAt(j);
                Character sourceChar = line.charAt(i+j);

                if (dictionary.get(keyChar) == null) {
                    if (!used.contains(sourceChar)) {
                        dictionary.put(keyChar, sourceChar);
                        used.add(sourceChar);
                    }else{
                        break;
                    }
                } else if (!dictionary.get(keyChar).equals(sourceChar)) {
                    break;
                }

                if (j == key.length() - 1) {
                    counter++;
                    if (counter == 1) {
                        startIndex = i;
                    }         
                }
            }
        }
        if (counter == 0) {
            System.out.println("0");
            return;
        }
        if (counter == 1) {
            System.out.println(line.substring(startIndex, startIndex + key.length()));
            return;
        }
        System.out.println(counter);
    }

    public static void main(String[] args) {
        ChasingSubs base = new ChasingSubs();
        Scanner scanner = new Scanner(System.in);
        base.decrypt(scanner.nextLine(), scanner.nextLine());
    }

}

Answer 1

Alternative approach

You are repeating a lot of work. Each time you advance a character, you rebuild the matching. But you don't need to do that. Instead create an array that says where to find the next instance of that character in the string.

public static int buildNextArray(String s) {
    int[] next = new int[s.length() - 1];
    for (int i = 0; i < next.length; i++) {
        next[i] = s.indexOf(s.charAt(i), i + 1) - i;
    }

    return next;
}

This converts the string into a unique array holding the relevant information: how far away is the next instance of that character in the string? Now, if the array you build for the decrypted key matches a portion of the array for the encrypted line, then it is a possible cipher match.

I'll leave the exact implementation for you to develop. Note that a negative number in the array for the key may match an unequal number in the array for the line. You may want to think about when it can match and when it can't match.

I would expect this approach to be faster because you can quickly see if a particular sequence matches by climbing the sequence for a particular letter. Consider the case where the input is

abcdefghijklmnopqrstuvwxyz
abca

In your version, you would match the first three letters to all twenty-three possible sequences and only find out on the fourth letter that it didn't work. With my suggestion, you would find out on the second letter that it won't work. And while there may be some inputs for which this is slower, the general result will be faster. Because starting with three or more different letters is more common than having the first and fourth letter the same.

It also saves the overhead of the HashSet and HashMap accesses. Instead, you can do array accesses.

Some other coding comments that won't affect performance:

Code to the interface

            HashMap<Character, Character> dictionary = new HashMap<>();
            HashSet<Character> used = new HashSet<>();

This could be

            Map<Character, Character> dictionary = new HashMap<>();
            Set<Character> used = new HashSet<>();

It won't matter much here, but in general, you want to code to the interface. It makes it easier to switch implementations later.

Delegate

        for (int i = 0; i < line.length() - key.length() + 1; i++) {
            HashMap<Character, Character> dictionary = new HashMap<>();
            HashSet<Character> used = new HashSet<>();

            for (int j = 0; j < key.length(); j++) {
                Character keyChar = key.charAt(j);
                Character sourceChar = line.charAt(i+j);

                if (dictionary.get(keyChar) == null) {
                    if (!used.contains(sourceChar)) {
                        dictionary.put(keyChar, sourceChar);
                        used.add(sourceChar);
                    }else{
                        break;
                    }
                } else if (!dictionary.get(keyChar).equals(sourceChar)) {
                    break;
                }

                if (j == key.length() - 1) {
                    counter++;
                    if (counter == 1) {
                        startIndex = i;
                    }         
                }
            }
        }

This gets a lot simpler if you make a helper method.

    public bool canMatch(String haystack, String needle) {
        Map<Character, Character> dictionary = new HashMap<>();
        Set<Character> used = new HashSet<>();

        for (int j = 0; j < needle.length(); j++) {
            Character keyChar = needle.charAt(j);
            Character sourceChar = haystack.charAt(j);

            if (dictionary.get(keyChar) == null) {
                if (used.contains(sourceChar)) {
                    return false;
                }

                dictionary.put(keyChar, sourceChar);
                used.add(sourceChar);
            } else if (!dictionary.get(keyChar).equals(sourceChar)) {
                return false;
            }
        }

        return true;
    }

I flipped around some of the internal logic. I find an if (false)/else structure confusing. I would rather check truth. And in this case, that also means that we can get rid of the else, as the original else clause finishes with a return (break). This has a side effect of reducing the indent on the other clause, which can sometimes be helpful.

Now, if the needle matches, we can return true. Otherwise, we return false. This allows us to change the caller

    for (int i = 0; counter == 0 && i < 1 + line.length() - key.length(); i++) {
         if (canMatch(line.substring(i), key)) {
             counter++;
             startIndex = i;
         }
    }

    if (counter == 0) {
        return "0";
    }

    for (int i = startIndex + 1; i < 1 + line.length() - key.length(); i++) {
        if (canMatch(line.substring(i), key)) {
            counter++;
        }
    }

    if (counter == 1) {
        return line.substring(startIndex, startIndex + key.length());
    }

    return Integer.toString(counter);

Now we don't have to compare j to the last index of the key on every iteration. The helper method will only return true when that was true.

I also changed the original method to return a string rather than print. Then the caller can do the print. This is a good habit that makes the method more flexible. Of course, it would be even better if we returned something other than a string, perhaps a result object.