CODEWITHSUNDEEP
stringalgorithmstring-matching
user5077148
user5077148

Reputation:

Test Cases for removing all occurrences in substring

Last week I was a giving a hackathon event for my college in which if given a string we need to delete the either first occurence or last occurence of substring,

Example s= "acaaac" and t ="a" s is the main string t is the substring

s could be either "caaac" or "acaac",we need to find maximum number of moves for given s and t

input only contains lowercase alphabetic letters [a-z]

Test case 1: s="aabb" and t = "ab" ,remove the occurence of t in "aabb" s becomes "ab" next remove the only occurrence of the string to get s ="" As there are no more occurrences in s of t we return 2

Test case 2: s="aabcd" t = "abc" --->only one occurence so count is 1,

Test Case 3: s="aa" t = "b" count =0

i tried following pseudo code in java

 count = 0   
 while(s.contains(t))
 {
 s=s.replacefirst(t,"")
 count++;
 }
 return count;

but i am not getting which test cases i am missing,i am passing 9 out of 14 in my event

Can i know which test cases am i missing?

Upvotes: 0

Views: 1619

Answers (2)

Raghu Kumar
Raghu Kumar

Reputation: 118

This can be easily solved using BFS and I don't think we can do better than brute force, maybe we can add optimizations of ignoring strings which got moves less than maxMoves while adding it to queue.

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
    }
}

Upvotes: 0

Selindek
Selindek

Reputation: 3423

Here is an example where your code will give a wrong answer:

s=ababaa , t=aba

You will remove first occurrence, what will result to:

(aba)baa -> baa -> 1

However if you remove the 2nd occurrence first then you can remove one additional substring:

ab(aba)a -> aba -> '' -> 2

It seems you have to iterate through all the possible combinations of first/last removing and choose the best result.

The more interesting question is if there is a better algorithm rather than brute force?

Upvotes: 2

Related Questions