All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Forbidden Pairs
Tag(s):
No tags
Problem
Editorial
Analytics

You are given a string S of integers(0 to 9) which represents a multicolored non-circular Garland made of flowers. Each integer from 0-9 in the string represents a  different color and each character of the string represents the color of that of particular flower. But there is a problem, some colors are considered  to be a bad match. If the garland contains one or more bad pairs then it is considered a bad garland i.e if 1 and 0 forms a bad pair then the string must not contain "01" or "10" as a substring.  Each color can have at most 1 bad match and any color cannot be its own bad match. 
You are Given K bad pairs. Find out the minimum numbers of flowers that must be removed to make the garland good.

Update: There are no spaces in the garland upon removing a flower, i.e if initially the string was "2120011" and you remove any one of the 0s the resulting string would become "212011".


INPUT

First-line contains string S of characters from(0-9) representing the garland

Second-line contains just one integer K representing the number of bad pairs

The next K lines contain two characters without any spaces between them representing the characters which make a bad match/bad pair.


CONSTRAINTS

1<=Lengthof(S)<=10^6

1<=K<=5


Output

Single line containing the minimum number of flowers that must be removed to make the garland good.

SAMPLE INPUT
1010123101
1
10
SAMPLE OUTPUT
3
Explanation

In the sample input we can see that we have only 1 forbidden pair "10", which can be removed by removing all three 0s. So the answer will be 3.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?