Tough Algorithm - Do not let the same character repeat for n positions

Question

I wasn't able to figure this one out since I don't know how to calculate "inserting" an underscore. I included my attempt at solving this problem.

Given a string, do not let the same character repeat for n positions. If it does repeat, insert an underscore to push it X positions down. The final output needed is just the total number of characters.

• Example 1) Input "QQ",2 becomes "Q__Q", the return value is 4.
• Example 2) Input "ABCA",2 becomes "ABCA" (no spaces needed), total characters is 4.
• Example 3) Input "DEDEE", 1 becomes "DEDE_E", total chars is 6.
• Example 4) Input "JKJK", 2 becomes "JK_JK", total characters is 5 (The toughest example).

import java.lang.Math;
import java.util.HashMap;
import java.util.ArrayList;

public class Spacer {
    public static void main (String args[]) {
        System.out.println("QQ,2 = " + spacey("QQ", 2) + ", expected 4");
        System.out.println("ABCA,2 = " + spacey("ABCA",2) + ", expected 4");
        System.out.println("DEDEE,1 = " + spacey("DEDEE", 1) + ", expected 6");
        System.out.println("JKJK,2 = " + spacey("JKJK", 2) + ", expected 5");
    }

    private static int spacey(String word, int spaces) {
        // int shift = 0;
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i=0; i<word.length(); i++) {
            char letter = word.charAt(i);
            System.out.println(i + "=" + letter + " last saw " + hm.get(word.charAt(i)));
            if (hm.get(letter) == null) {
                hm.put(letter, i);
            } else {
                System.out.println(i + "-" + hm.get(letter) + "<=" + spaces);
                if (i - hm.get(word.charAt(i)) <= spaces) {
                    // System.out.println("add " + (spaces + 1 - (i - hm.get(letter))));
                    // shift += (spaces + 1) - (i - hm.get(letter));
                    word = word.substring(0, i) + "_" + word.substring(i);
                    System.out.println(i + " word=" + word);
                }
                hm.put(letter, i);      // update the hashmap with the last seen again
            }
        }
        return word.length();
    }
}

Answer 1

The requirement doesn't ask you to display the constructed string so we need to only do calculations. The regex (.+)\1 will match any repetition of 1 or more chars and countPattern returns how many times that pattern was found.

    public static void main(String[] args) {
        System.out.println("QQ,2 = " + spacey("QQ", 2) + ", expected 4");
        System.out.println("ABCA,2 = " + spacey("ABCA",2) + ", expected 4");
        System.out.println("DEDEE,1 = " + spacey("DEDEE", 1) + ", expected 6");
        System.out.println("JKJK,2 = " + spacey("JKJK", 2) + ", expected 6");   //in becomes JK__JK, ie. 4 + 2x'_'
    }

    private static int spacey(String word, int spaces) {
        if(spaces<0){
            throw new IllegalArgumentException("should be positive value");
        }
        if(word==null){
            return 0;
        }
        if(spaces==0){
            return word.length();
        }
        final Pattern repeatedCharRegex = Pattern.compile("(.+)\\1");
        final int repetitions = countPattern(word, repeatedCharRegex);
        return word.length() + repetitions*spaces;
    }

    public static int countPattern(String references, Pattern referencePattern) {
        Matcher matcher = referencePattern.matcher(references);
        int count = 0;
        while (matcher.find()){
            count++;
        }
        return count;
    }

Answer 2

Your question is (mainly) about inserting underscores. A key insight that can help move forward is that the input and output strings are different, so it would be cleaner to treat them as such, using a StringBuilder for example. Additionally, it doesn't hurt at this stage to use temporary variables to capture concepts such as distance between characters. Leveraging these two ideas, you can have more self-explanatory code, for example:

public static String space(String input, int spaces) {
    HashMap<Character, Integer> map = new HashMap<>();
    StringBuilder result = new StringBuilder();
    for( char symbol : input.toCharArray() ) {
        int position = result.length();
        int lastPosition = map.getOrDefault(symbol, position-spaces-1);
        int distance = position - lastPosition -1;
        for( int j = 0; j < Math.max( spaces - distance, 0) ; j++ ) {
            result.append('_');
        }
        result.append(symbol);
        map.put(symbol, result.length()-1);
    }
    return result.toString();
}

(and once this is mastered and digested, it's of course possible to in-line the temps)

Answer 3

First of all you have an error in one of your test cases. Assuming you want to reproduce the cases in the quoted challenge, you need a 1 as second argument to the call to spacey here:

    System.out.println("DEDEE,1 = " + spacey("DEDEE", 1) + ", expected 6");
    //                        ^                       ^

The formula to calculate the number of underscores to insert is:

    previousindex + n + 1 - i

...where previousindex is the index at which the current letter occurred before, and i is the current index.

You can repeat an underscore with the .repeat string method. Don't forget to update i afterwards, so it keeps pointing to the currently processed character (which moved forward).

So your code could work like this:

import java.lang.Math;
import java.util.HashMap;
import java.util.ArrayList;

public class Spacer {
    public static void main (String args[]) {
        System.out.println("QQ,2 = " + spacey("QQ", 2) + ", expected 4");
        System.out.println("ABCA,2 = " + spacey("ABCA",2) + ", expected 4");
        System.out.println("DEDEE,1 = " + spacey("DEDEE", 1) + ", expected 6");
        System.out.println("JKJK,2 = " + spacey("JKJK", 2) + ", expected 5");
    }

    private static int spacey(String word, int spaces) {
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i=0; i<word.length(); i++) {
            char letter = word.charAt(i);
            if (hm.get(letter) == null) {
                hm.put(letter, i);
            } else {
                int underscores = hm.get(letter) + spaces + 1 - i;
                if (underscores > 0) { // Need to add underscores
                    word = word.substring(0, i) + "_".repeat(underscores) + word.substring(i);
                    i += underscores; // update i so it still points to the current character
                }
                hm.put(letter, i);
            }
        }
        return word.length();
    }
}