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 :



title-img


                            Solution in C :

In C++ :





/*
*/

//#pragma comment(linker, "/STACK:16777216")
#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 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];
			}
			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[3];
           
        
    }
    
    
}

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);
                g.add(last);
            } else {
                last.n++;
            }
        }
        
        for (int i = 0; i < g.size(); i++){
            CharGroup cg = g.get(i);
            cg.removeCount[1] = i+1;
            if (i > 0) {
                cg.removeCount[2] = 
                    g.get(i-1).removeCount[2]+
                    g.get(i-1).removeCount[1];
            }
            if (cg.n >= 2) {
                cg.removeCount[2]++;
            }
            if ((i>=2)&&(g.get(i-1).n==1)&&
                (cg.c == g.get(i-2).c)) {
                cg.removeCount[2]--;
            }
        }
        
        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;
  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)
                        




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 →