# 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.

Constraints
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++ :

/*
*/

#define _CRT_SECURE_NO_WARNINGS

#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 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];
}
res.insert(temp);
}
}

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;
else
{
v.push_back(cnt);
cnt = 1;
}
}
v.push_back(cnt);
for (int i = 0; i < v.size(); i++)
{
if (v[i]>1)
++ans;
}

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

int main(){
//	freopen("hospital.in","r",stdin);
//	freopen("hospital.out","w",stdout);
//freopen("F:/in.txt", "r", stdin);
//freopen("F:/output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin >> st;
//	cout << naive(st) << endl;

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

In Java :

import java.io.*;
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;

}

}

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();

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 {
last.n++;
}
}

for (int i = 0; i < g.size(); i++){
CharGroup cg = g.get(i);
cg.removeCount = i+1;
if (i > 0) {
cg.removeCount =
g.get(i-1).removeCount+
g.get(i-1).removeCount;
}
if (cg.n >= 2) {
cg.removeCount++;
}
if ((i>=2)&&(g.get(i-1).n==1)&&
(cg.c == g.get(i-2).c)) {
cg.removeCount--;
}
}

System.out.printf("%d\n", g.get(g.size()-1).removeCount);
}
}

In C :

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

int main(){
int len,cs,i;
long long ans;
scanf("%s",str);
len=strlen(str);
for(i=cs=0;i<len;i++){
if(!i || str[i]!=str[i-1])
count[cs++]=1;
else
count[cs-1]++;
if(i && i<len-1 && str[i]!=str[i-1] && str[i-1]==str[i+1])
mark[cs-1]=1;
}
for(i=ans=0;i<cs;i++){
ans+=i;
if(count[i]>1)
ans++;
if(mark[i])
ans--;
}
printf("%lld",ans);
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

else:
block_size += 1

prev2 = prev
prev = c

print(ncr(n_blocks, 2) + count)```
```

## 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

## 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

## 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

## 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

## 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

## 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