How to find the max moves using math?

Question

I am designing a game; Here I need to find max score for that I need to find max moves player can make.

for example -

playerA-value = abccd I need to find the substring say bc in playerA-value

Now I deleted it. So playerA-value = acd

algorithm checks for bc and it not found, so max move = 1.

for example -

playerA-value = aeerrb I need to find the substring say er in playerA-value

Now I deleted it. So playerA-value = aerb

algorithm checks for er and it found, above steps repeats, finally max move = 2.

to maximize the score, I can delete it either from the front end of the string or rear end, or combination of both(like first few time front, later check for the back side.

Is there any formula in combination or permutation to find this?

Answer 1

I wrote the following Java code to output the maximum number of removals of a substring from a string.

The code uses replaceFirst within a while loop, until it can no longer be applied. The code counts the number of times the while loop executes, and this is the integer output.

public class RemoveString {

    public static int maxScore(String bigString, String littleString){
        String tempString = bigString;
        int runningCount = 0;
        while(!(tempString.replaceFirst(littleString, "").equals(tempString))){
            tempString = tempString.replaceFirst(littleString, "");
            runningCount++;
        }
        return runningCount;
    }

    public static void main(String[] args){
        System.out.println(maxScore("ababa", "er")); // Should be 0
        System.out.println(maxScore("abaer", "er")); // Should be 1
        System.out.println(maxScore("erababa", "er")); // Should be 1
        System.out.println(maxScore("zzzeraba", "er")); // Should be 1
        System.out.println(maxScore("aerbabaer", "er")); // Should be 2
        System.out.println(maxScore("aeerra", "er")); // Should be 2
        System.out.println(maxScore("aerera", "er")); // Should be 2
        System.out.println(maxScore("aerbera", "er")); //Should be 2
        System.out.println(maxScore("aberebraba", "er")); // Should be 1

    }
}

I ran the test code, and all nine test cases gave the expected output.