Ytukyg

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?

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.

This can be easily solved using BFS. The following code gives the correct output for all the inputs mentioned above. I've used JUnit.Assert.assertEquals().

import java.util.Deque;

import java.util.LinkedList;

import static org.junit.Assert.assertEquals;



public class RemoveString {

    static class Moves {

        String str ;

        int moves ;

        public Moves(String str, int moves) {

            this.str = str ;

            this.moves = moves ;

        }

    }



    static

    public int maxMoves(String s, String t) {

        int max = 0 ;

        if (s == null || t == null || t.length() > s.length())

            return max ;

        Deque<Moves> q = new LinkedList<>() ;

        q.offer(new Moves(s, 0)) ;

        while (!q.isEmpty()) {

            for (int sz = q.size() ;  sz > 0 ; -- sz) {

                Moves curMove = q.poll() ;

                max = Math.max(max, curMove.moves) ;

                if (curMove.str.contains(t)) {

                    int nextStart = curMove.str.indexOf(t, 0) ;

                    if (nextStart != -1) {

                        q.offer(new Moves(curMove.str.substring(0, nextStart) + curMove.str.substring(nextStart+t.length()), curMove.moves+1)) ;

                    }

                    int lastStart = curMove.str.lastIndexOf(t, curMove.str.length()) ;

                    if (lastStart != -1) {

                        q.offer(new Moves(curMove.str.substring(0, lastStart) + curMove.str.substring(lastStart+t.length()), curMove.moves+1)) ;

                    }

                }

            }

        }

        return max ;

    }



    public static void main(String args) {

        assertEquals(3, maxMoves("babba", "b"));

        assertEquals(2, maxMoves("aabb", "ab"));

        assertEquals(2, maxMoves("ababaa", "aba"));

        assertEquals(1, maxMoves("abaer", "er")); // Should be 1

        assertEquals(1, maxMoves("erababa", "er")); // Should be 1

        assertEquals(1, maxMoves("zzzeraba", "er")); // Should be 1

        assertEquals(2, maxMoves("aerbabaer", "er")); // Should be 2

        assertEquals(2, maxMoves("aeerra", "er")); // Should be 2

        assertEquals(2, maxMoves("aerera", "er")); // Should be 2

        assertEquals(2, maxMoves("aerbera", "er")); //Should be 2

        assertEquals(1, maxMoves("aberebraba", "er")); // Should be 1

    }

}