Beautiful Strings – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Beautiful Strings HackerRank Solution
#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;
}
Java Beautiful Strings HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private static InputReader in;
private static PrintWriter out;
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
char[] c = in.next().toCharArray();
int n = c.length;
long[][] dp = new long[n][3];
long[][] x = new long[n][3];
dp[0][0] = 1;
dp[0][1] = 1;
dp[0][2] = 0;
x[0][0] = 1;
x[0][1] = 0;
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1] + dp[i-1][0];
if (c[i-1] == c[i]) dp[i][1] -= dp[i-1][0];
dp[i][2] = dp[i-1][2] + dp[i-1][1];
if (c[i-1] == c[i]) dp[i][2] -= x[i-1][1];
if (i >= 2 && c[i-2] == c[i]) dp[i][2] -= x[i-2][0];
if (i >= 2 && c[i-1] == c[i-2] && c[i] == c[i-1]) dp[i][2] += x[i-1][0];
x[i][0] = 1;
x[i][1] = x[i-1][1];
if (i == 1) x[i][1]++;
else if (c[i-2] != c[i-1]) x[i][1] += x[i-2][0];
// System.out.println(i+" "+Arrays.toString(dp[i]));
}
// HashSet<String> s = new HashSet<>();
// for (int i = 0; i < n; i++) {
// for (int j = i+1; j < n; j++) {
// String xx = new String(c, 0, i) + new String(c, i+1, j-i-1) + new String(c, j+1, n-j-1);
// s.add(xx);
// }
// }
out.println(dp[n-1][2]);
// out.println(s.size());
out.close();
System.exit(0);
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Python 3 Beautiful Strings HackerRank Solution
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)
Python 2 Beautiful Strings HackerRank Solution
s = raw_input()
n = len(s)
res = [[0]*3 for i in xrange(3)]
for i in xrange(n+1):
for k in xrange(3):
t = 0
if k == i:
t = 1
elif k < i:
c = set()
for p in xrange(i-1,i-k-2,-1):
if s[p] not in c:
c.add(s[p])
t += res[p%3][k-(i-1-p)]
res[i%3][k] = t
print res[n%3][2]
C Beautiful Strings HackerRank Solution
#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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below