# PAT Advanced 1093 Count PAT’s: DP + Constant Space

## Overview

PAT Advanced 1093 Count PAT’s is solved by dynamic programming (DP) using constant space as the states only depends on previous one, Java is too slow to AC.

## PAT Advanced 1093 Count PAT’s

The string APPAPT contains two PAT‘s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT‘s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT‘s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

`APPAPT`

Sample Output:

`2`

## Solution: DP + Constant Space

The key is to find the recursive definition/DP function of the counts of PAT within the given string. And the problem is simplified by the fact that it only contains 3 characters {P, A, T}, so the recursive function is easier to derive by considering the last char within the string, and the results of a string of length n could be calculated from the results of the string of length n – 1, and we do not need to allocate an array to store those temporary results, the following C++ code could be accepted by PAT OJ for this 1093 Count PAT’s problem but the java code with the exact same logic can not pass because Java is still too slow:

```#include <iostream>

const long long MOD_NUMBER = 1000000007l;

long long countPATs(const std::string s) {
long long pCounts = 0L;
long long paCounts = 0L;
long long patCounts = 0L;

int len = s.size();
if (len < 3) {
return 0;
}

for (int i = 3; i <= len; ++i) {
pCounts = (s[i - 3] == 'P' ? pCounts + 1 : pCounts);
paCounts = (s[i - 2] == 'A' ?
(paCounts % MOD_NUMBER + pCounts % MOD_NUMBER) % MOD_NUMBER: paCounts);
patCounts = (s[i - 1] == 'T') ? (patCounts % MOD_NUMBER + paCounts % MOD_NUMBER) : patCounts;
}
return patCounts % MOD_NUMBER;
}

int main() {
std::string str;
std::cin >> str;
std::cout << countPATs(str);
return 0;
}
```

And I give the Java code too, but unfortunately, it cannot be accepted because of TLE, if anyone could give a Java solution to pass the OJ, that would be awesome and greatly appreciated.

```import java.util.Scanner;

/**
* @author Sigmainfy
*/

public class Main {

public static final long MOD_NUMBER = 1000000007L;

private static long countPATs(final String s) {
long pCounts = 0L;
long paCounts = 0L;
long patCounts = 0L;

int len = s.length();
if (len < 3) {
return 0;
}

for (int i = 3; i <= len; ++i) {
pCounts = (s.charAt(i - 3) == 'P' ? pCounts + 1 : pCounts);
paCounts = (s.charAt(i - 2) == 'A' ?
(paCounts % MOD_NUMBER + pCounts % MOD_NUMBER) % MOD_NUMBER: paCounts);
patCounts = (s.charAt(i - 1) == 'T') ? (patCounts % MOD_NUMBER + paCounts % MOD_NUMBER) : patCounts;
}
return patCounts % MOD_NUMBER;
}

public static void main(String [] args) {
Scanner scanner = new Scanner(System.in);
System.out.println(countPATs(scanner.next()));
scanner.close();
}
}
```