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