## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Special Palindrome Again Challenge

Sharing is caring!

Problem Statement
A string is said to be a special palindromic string if either of two conditions is met:
* All of the characters are the same, e.g. `aaa`.
* All characters except the middle one are the same, e.g. `aadaa`.

A specialpalindromic substring is any substring of a string which meets one of those criteria. Given a string, determine how many special palindromic substrings can be formed from it.

For example, given the string `s=mnonopoo`, we have the following special palindromic substrings: `{m, n, o, n, o, p, o, o, non, ono, opo, oo}`.

Function Description
Complete the `substrCount` function. It should return an integer representing the number of special palindromic substrings that can be formed from the given string.

`substrCount` has the following parameter(s):
* `n`: an integer, the length of string s
* `s`: a string

Input Format
The first line contains an integer, `n`, the length of `s`.
The second line contains the string `s`.

Constraints
* $1 \le n \le 10^6$
* Each character of the string is a lowercase alphabet, `ascii[a-z]`.

Sample Input 0

``````5
asasd
``````

Sample Output 0

``````7
``````

Explanation 0
The special palindromic substrings of `s=asasd` are `{a, s, a, s, d, asa, sas}`.

Solution

```import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class SpecialPalindromeAgain {

static Map bruteforce(int n, String s) {
Map result = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int len = 1; len <= n - i; len++) {
String substr = s.substring(i, i + len);

if (substr.length() == 1) {
if (!result.containsKey(substr)) {
result.put(substr, 0l);
}
result.put(substr, result.get(substr) + 1);
} else if (substr.length() > 0 && substr.length() % 2 == 0) {
boolean allSame = true;
for (int j = 1; j < substr.length(); j++) {
if (substr.charAt(j) != substr.charAt(j - 1)) {
allSame = false;
break;
}
if (allSame) {
if (!result.containsKey(substr)) {
result.put(substr, 0l);
}
result.put(substr, result.get(substr) + 1);
}
}
} else if (substr.length() > 0 && substr.length() % 2 == 1) {
int mid = substr.length() / 2;
String left = substr.substring(0, mid);
String right = substr.substring(mid + 1);
if (left.equals(right)) {
if (!result.containsKey(substr)) {
result.put(substr, 0l);
}
result.put(substr, result.get(substr) + 1);
}
}
}
}

return result;
}

static long substrCount(int n, String s) {
long ans = 0;

for (int i = 0; i < n; i++) {
ans++;
char previousChar = s.charAt(i);
int charsLeftCount = 1;
int charsRightCount = 0;
boolean reachedMiddle = false;

for (int j = i + 1; j < n; j++) {
char ch = s.charAt(j);
if (!reachedMiddle && ch != previousChar) {
reachedMiddle = true;
} else if (reachedMiddle && (ch != previousChar || j == n - 1)) {
if (j == n - 1 && ch == previousChar) {
charsRightCount++;
}

if (charsLeftCount == charsRightCount) {
ans++;
}

break;
} else if (!reachedMiddle && ch == previousChar) {
charsLeftCount++;
if (charsLeftCount >= 2) {
ans++;
}
} else if (reachedMiddle && ch == previousChar) {
charsRightCount++;
if (charsLeftCount == charsRightCount) {
ans++;
break;
}
}
}
}

return ans;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in3.txt"));

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String s = scanner.next();

long startTime = System.currentTimeMillis();
long result = substrCount(n, s);
long endTime = System.currentTimeMillis();

System.out.println("Took " + (endTime - startTime) + " ms");

Scanner expectedScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "expected3.txt"));
long expected = expectedScanner.nextLong();
if (result != expected) {
System.out.println("Error: expected " + expected + " got " + result);
} else {
System.out.println("Correct: expected " + expected + " got " + result);
}
}
}
```