HackerRank Beautiful Strings Problem Solution
In this post, we will solve HackerRank Beautiful Strings Problem Solution.
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.
Output Format
Print the number of different strings that are beautiful with respect to S.
Sample Input
abba
Sample Output
4Explanation
S = {abba}
The following strings can be derived by removing 2 characters from S: ab, bb, ba, ab, ba, aa, and bb.
This gives us our set of unique beautiful strings, B= {ab, ba, aa, bb}. As |B|= 4, we print 4.
Beautiful Strings C Solution
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#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;
}Beautiful Strings C++ Solution
#include <bits/stdc++.h>
using namespace std;
/*
* Complete the 'beautifulStrings' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts STRING s as parameter.
*/
long long beautifulStrings(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()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ofstream fout(getenv("OUTPUT_PATH"));
string s;
getline(cin, s);
long result = beautifulStrings(s);
fout << result << "\n";
fout.close();
return 0;
}Beautiful Strings C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'beautifulStrings' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts STRING s as parameter.
*/
public static long beautifulStrings(string st)
{
int cnt = 0;
List<int> v = new List<int>();
long ans = 0;
for (int i = 0; i < st.Length; i++)
{
if (i == 0 || st[i] == st[i - 1])
{
++cnt;
}
else
{
v.Add(cnt);
cnt = 1;
}
}
v.Add(cnt);
for (int i = 0; i < v.Count; i++)
{
if (v[i] > 1)
{
++ans;
}
}
for (int i = 1; i + 1 < st.Length; i++)
{
if (st[i - 1] == st[i + 1] && st[i] != st[i - 1])
{
--ans;
}
}
ans += v.Count * 1l * (v.Count - 1) / 2;
return ans;
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string s = Console.ReadLine();
long result = Result.beautifulStrings(s);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Beautiful Strings Java Solution
import java.io.*;
public class Solution {
static long beautifulStrings(char[] s) {
long result = 0;
int res[] = new int[s.length];
for (int j = s.length-1; j > 0; j--) {
res[j-1] = res[j];
if ((j > 1) && (s[j] == s[j-1])) {
continue;
}
res[j-1]++;
result++;
}
for (int i = 1; i < s.length-1; i++) {
if (s[i] == s[i-1]) {
continue;
}
if (s[i+1] != s[i-1]) {
result++;
}
result += res[i+1];
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
char[] s = br.readLine().toCharArray();
long result = beautifulStrings(s);
bw.write(String.valueOf(result));
bw.newLine();
bw.close();
br.close();
}
}Beautiful Strings JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'beautifulStrings' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts STRING s as parameter.
*/
function beautifulStrings(s) {
// Write your code here
let first;
let second;
let extra;
let unique = 0;
let doubles = 0;
let catch22 = 0;
for(let i = 0;i<s.length;i++){
if (first !== s[i]){
if(i>0 && i<s.length && s[i+1] === extra){
catch22 ++;
unique ++;
first = s[i];
extra = s[i];
second = 0;
} else {
unique ++;
first = s[i];
extra = s[i];
second = 0;
}
} else if (second !== s[i]){
doubles ++;
second = s[i];
} else {
second = s[i];
}
}
let total = 0;
if(unique == 1){
return(1);
} else {
for(let j=0;j<unique;j++){
total+=j;
};
total += doubles - catch22;
return(total)
}
};
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const s = readLine();
const result = beautifulStrings(s);
ws.write(result + '\n');
ws.end();
}Beautiful Strings Python Solution
import itertools
s = input()
groups = [(c, sum(1 for x in l)) for c, l in itertools.groupby(s)]
multiple = sum(x[1] > 1 for x in groups)
fence = sum(groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1
for i in range(1, len(groups) - 1))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)
