Beautiful Strings

Problem Statement :

You are given a string, S, consisting of lowercase English letters.

A string is beautiful with respect to S if it can be derived from S by removing exactly 2 characters.

Find and print the number of different strings that are beautiful with respect to S.

Input Format

A single string of lowercase English letters denoting S.

3 <= |S| <= 10^6
3 <= |S| <= 20  holds for test cases worth at least 15% of the problem's score.
3 <= |S| <= 2000 holds for test cases worth at least  of the problem's score.
Output Format

Print the number of different strings that are beautiful with respect to S.

Solution :


                            Solution in C :

In C++ :


//#pragma comment(linker, "/STACK:16777216")

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

const int N = 1031;

using namespace std;

string st;
int naive(string st)
	set<string> res;
	for (int i = 0; i < st.size(); i++)
		for (int j = i + 1; j < st.size(); j++)
			string temp = "";
			for (int q = 0; q < st.size(); q++)
				if (q != i&&q != j)
					temp += st[q];

	set<string>::iterator it;
	/*for (it = res.begin(); it != res.end(); it++)
		cout << *it << endl;
	return res.size();

long long smart(string st)
	int cnt = 0;
	vector<int> v;
	long long ans = 0;
	for (int i = 0; i < st.size(); i++)
		if (i == 0 || st[i] == st[i - 1])
			cnt = 1;
	for (int i = 0; i < v.size(); i++)
		if (v[i]>1)

	for (int i = 1; i +1< st.size(); i++)
		if (st[i - 1] == st[i + 1] && st[i] != st[i - 1])
	ans += v.size() * 1ll * (v.size() - 1) / 2;
	return ans;

int main(){
//	freopen("","r",stdin);
//	freopen("hospital.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	cin >> st;
//	cout << naive(st) << endl;

	cout << smart(st) << endl;
	cin.get(); cin.get();
	return 0;

In Java :

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class CharGroup {
    public char c;
    public int n;
    public long [] removeCount;
    CharGroup(char ch) {
        c = ch;
        n = 1;
        removeCount = new long[3];

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(;
        String s =;
        CharGroup last = null;
        ArrayList<CharGroup> g = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char nc = s.charAt(i);
            if ((i == 0) || (last.c != nc)) {
                last = new CharGroup(nc);
            } else {
        for (int i = 0; i < g.size(); i++){
            CharGroup cg = g.get(i);
            cg.removeCount[1] = i+1;
            if (i > 0) {
                cg.removeCount[2] = 
            if (cg.n >= 2) {
            if ((i>=2)&&(g.get(i-1).n==1)&&
                (cg.c == g.get(i-2).c)) {
        System.out.printf("%d\n", g.get(g.size()-1).removeCount[2]);

In C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char str[1000001];
int count[1000000],mark[1000000]={0};

int main(){
  int len,cs,i;
  long long ans;
    if(!i || str[i]!=str[i-1])
    if(i && i<len-1 && str[i]!=str[i-1] && str[i-1]==str[i+1])
  return 0;

In Python3 :

import operator as op
import functools

def ncr(n, r):
    if n < r: return 0
    r = min(r, n-r)
    if r == 0: return 1
    numer = functools.reduce(op.mul, range(n, n-r, -1))
    denom = functools.reduce(op.mul, range(1, r+1))
    return numer//denom

s = input()
s += ' '
n_blocks = 0
block_size = 0
count = 0
prev = None
prev2 = None
for c in s:
    if prev and c != prev:
        if block_size > 1:
            count += 1
        n_blocks += 1
        block_size = 1
        if c == prev2:
            count -= 1        
        block_size += 1
    prev2 = prev
    prev = c

print(ncr(n_blocks, 2) + count)

View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →