Connection Status:
Competition Arena > Softmatchd2

Softmatchd2

SRM 709 · 2016-12-07 · by subscriber

SRM 709 · 2016-12-07 · by subscriber · Dynamic Programming
Class Name: Softmatchd2
Return Type: int
Method Name: count
Arg Types: (string, string)
Problem Statement

Problem Statement

Hero has a String pattern. Each character in pattern is one of '0', '1', '2', and '3'. Hero also has a String S of wildcard characters. Each character of S is either 'a' or 'b'. You are allowed to modify S by changing some (possibly none or all) characters to their uppercase versions: that is 'a' to 'A' and 'b' to 'B'. The meaning of the wildcard characters in S is as follows:
  • 'a' matches small digits: '0' and '1'
  • 'A' matches big digits: '2' and '3'
  • 'b' matches even digits: '0' and '2'
  • 'B' matches odd digits: '1' and '3'
We say that S contains an occurrence of pattern at position j if for each valid i the wildcard character S[j+i] exists and matches the digit pattern[i]. As we already mentioned above, you are allowed to modify S by changing some of its letters to uppercase. Your goal is to maximize the total number of occurrences of pattern in your modified S. Return the largest possible number of occurrences.

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • Each character in S will be either 'a' or 'b'.
  • pattern will contain between 1 and 50 characters, inclusive.
  • Each character in pattern will be between '0' and '3', inclusive.
  • pattern will be at most as long as S.
Examples
0)
"aba"
"13"
Returns: 2

The string "aBA" contains two occurrences of the given pattern: one at position 0 and the other at position 1.

1)
"abbaa"
"123"
Returns: 2

One string that contains two occurrences of the given pattern is the string "abBAA". One occurrence is at position 0 (small digit, even digit, odd digit), the other is at position 2 (odd digit, large digit, large digit).

2)
"aaaa"
"1230"
Returns: 1
3)
"ababbaaba"
"0311"
Returns: 3
4)
"aabbbabbbb"
"332233"
Returns: 2

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Softmatchd2 with a public method int count(string S, string pattern) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous