Table of Contents
Morgan and a String – 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++ Morgan and a String HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
class SuffixArray {
public:
typedef char Alpha;
typedef int Index;
void build(const Alpha *str, Index n, int AlphaSize);
void build(const Alpha *str, Index n);
inline Index getKThSuffix(Index k) const { return suffixArray[k]; }
inline Index length() const { return suffixArray.size() - 1; }
std::vector<Index> suffixArray;
template<typename AlphaT> void sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets);
template<typename AlphaT> void inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector<Index> &bucketOffsets);
template<typename AlphaT> void countingAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b = false);
template<typename AlphaT> void getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets);
void buildInverseSuffixArray();
std::vector<Index> inverseSuffixArray;
};
void SuffixArray::build(const Alpha *str, Index n, int AlphaSize) {
suffixArray.resize(n+1);
if(n == 0) suffixArray[0] = 0;
else {
//I = sizeof(Index) * CHAR_BITS ???
//suffixArray + bucketOffsets + types + ????????
//= n*I + max(AlphaSize, n/2)*I + 2*n + O(log n) bits
//I = 4 * 32?AlphaSize??????????:
//(6+1/16) * n + O(log n) bytes
std::vector<Index> bucketOffsets(std::max(AlphaSize, (n+1) / 2) + 1);
sa_is<Alpha>(str, n, AlphaSize, &suffixArray[0], bucketOffsets);
}
}
void SuffixArray::build(const Alpha *str, Index n) {
Alpha maxElem = *std::max_element(str, str + n);
assert(maxElem+0 < std::numeric_limits<int>::max());
build(str, n, (int)(maxElem+1));
}
//str?[0,n)?????????????sa?[0,n]???
template<typename AlphaT>
void SuffixArray::sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets) {
std::vector<bool> types(n+1);
types[n-1] = 0; types[n] = 1;
for(Index i = n-2; i >= 0; i --)
types[i] = str[i] < str[i+1] || (str[i] == str[i+1] && types[i+1]);
countingAlphabets(str, n, AlphaSize, bucketOffsets);
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
std::fill(sa, sa + n + 1, -1);
for(Index i = 1; i < n; i ++)
if(types[i] && !types[i-1]) sa[-- bucketOffsets[(int)str[i]]] = i;
sa[0] = n;
inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
Index n1 = 0;
for(Index i = 0; i <= n; i ++) {
Index j = sa[i];
if(j > 0 && types[j] && !types[j-1]) sa[n1 ++] = j;
}
//LMS substrings????????sa[0..n1-1]??????????
//???????sa???????????????
//??????pos????????????????????
//???LMS substring????????????LMS substring???n/2????????????????1???????
Index *buffer = sa + n1;
std::fill(buffer, sa + n + 1, -1);
Index uniqueLMSCount = 0, prevPos = -1;
assert(sa[0] == n);
buffer[sa[0] / 2] = uniqueLMSCount ++; //'$'
for(Index i = 1; i < n1; i ++) {
Index pos = sa[i]; bool diff = false;
if(prevPos == -1) diff = true;
else for(Index j = pos, k = prevPos; ; j ++, k ++) {
if(str[j] != str[k] || types[j] != types[k]) {
diff = true;
break;
}else if(j != pos && ((types[j] && !types[j-1]) || (types[k] && !types[k-1])))
break;
}
if(diff) {
uniqueLMSCount ++;
prevPos = pos;
}
buffer[pos / 2] = uniqueLMSCount - 1;
}
for(Index i = n, j = n; i >= n1; i --)
if(sa[i] >= 0) sa[j --] = sa[i];
Index *sa1 = sa, *s1 = sa + n + 1 - n1;
if(uniqueLMSCount == n1)
for(Index i = 0; i < n1; i ++) sa1[s1[i]] = i;
else
sa_is<Index>(s1, n1 - 1, uniqueLMSCount, sa1, bucketOffsets);
countingAlphabets(str, n, AlphaSize, bucketOffsets);
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
for(Index i = 1, j = 0; i <= n; i ++)
if(types[i] && !types[i-1]) s1[j ++] = i;
for(Index i = 0; i < n1; i ++) sa1[i] = s1[sa1[i]];
std::fill(sa + n1, sa + n + 1, -1);
for(Index i = n1-1; i >= 1; i --) {
Index j = sa[i]; sa[i] = -1;
sa[-- bucketOffsets[(int)str[j]]] = j;
}
inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
}
template<typename AlphaT>
void SuffixArray::inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector<Index> &bucketOffsets) {
getBucketOffsets(str, n, false, AlphaSize, bucketOffsets);
for(Index i = 0; i < n; i ++) {
Index j = sa[i] - 1;
if(j >= 0 && !types[j]) sa[bucketOffsets[(int)str[j]] ++] = j;
}
getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
for(Index i = n; i >= 1; i --) {
Index j = sa[i] - 1;
if(j >= 0 && types[j]) sa[-- bucketOffsets[(int)str[j]]] = j;
}
}
template<typename AlphaT>
void SuffixArray::countingAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b) {
if(b || (int)bucketOffsets.size() / 2 >= AlphaSize) {
std::vector<Index>::iterator alphabetCounts =
b ? bucketOffsets.begin() : bucketOffsets.begin() + AlphaSize;
std::fill(alphabetCounts, alphabetCounts + AlphaSize, 0);
for(Index i = 0; i < n; i ++)
alphabetCounts[(int)str[i]] ++;
}
}
template<typename AlphaT>
void SuffixArray::getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets) {
//AlphaSize????????bucketOffset??????alphabet??????????????
//AlphaSize????????bucketOffset?alphabetCounts??????????????
std::vector<Index>::iterator alphabetCounts;
if((int)bucketOffsets.size() / 2 < AlphaSize) {
countingAlphabets(str, n, AlphaSize, bucketOffsets, true);
alphabetCounts = bucketOffsets.begin();
}else alphabetCounts = bucketOffsets.begin() + AlphaSize;
Index cumsum = 1; //'$'??
if(dir) {
for(int i = 0; i < AlphaSize; i ++) {
cumsum += alphabetCounts[i];
bucketOffsets[i] = cumsum;
}
}else {
for(int i = 0; i < AlphaSize; i ++) {
Index x = alphabetCounts[i];
bucketOffsets[i] = cumsum;
cumsum += x;
}
}
}
void SuffixArray::buildInverseSuffixArray() {
Index n = length();
inverseSuffixArray.resize(n+1);
for(Index i = 0; i <= n; i ++)
inverseSuffixArray[suffixArray[i]] = i;
}
struct StringInterspersal {
string minimum(vector <string> W) {
int n = W.size();
string w; vi d;
rep(i, n) {
d.pb(w.size());
w += W[i];
w += '~';
}
SuffixArray sa;
sa.build(&w[0], w.size());
sa.buildInverseSuffixArray();
vi v(n);
string s;
while(1) {
pair<int,int> p(INF,-1);
rep(i, n) if(v[i] != W[i].size()) {
p = min(p, mp(sa.inverseSuffixArray[d[i] + v[i]], i));
}
if(p.second == -1) break;
s += W[p.second][v[p.second]];
v[p.second] ++;
}
return s;
}
};
char A[100001], B[100001];
int main() {
int T;
scanf("%d", &T);
rep(ii, T) {
scanf("%s", A);
scanf("%s", B);
string w; vi d;
d.pb(w.size()), w += A, w += '~';
d.pb(w.size()), w += B, w += '~';
SuffixArray sa;
sa.build(&w[0], w.size());
sa.buildInverseSuffixArray();
vi v(2);
priority_queue<pair<int,int>,vpii,greater<pii> > q;
rep(i, 2) q.push(mp(sa.inverseSuffixArray[d[i] + v[i]], i));
string ans;
while(!q.empty()) {
int i = q.top().second; q.pop();
ans += w[d[i] + v[i]];
v[i] ++;
if(w[d[i] + v[i]] != '~')
q.push(mp(sa.inverseSuffixArray[d[i] + v[i]], i));
}
puts(ans.c_str());
}
return 0;
}
Java Morgan and a String HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni();T >= 1;T--){
char[] s = ns().toCharArray();
char[] t = ns().toCharArray();
int p = 0, q = 0, r = 0;
char[] ret = new char[s.length+t.length];
outer:
while(r < ret.length){
if(q == t.length){
ret[r++] = s[p++];
}else if(p == s.length){
ret[r++] = t[q++];
}else if(s[p] < t[q]){
ret[r++] = s[p++];
}else if(s[p] > t[q]){
ret[r++] = t[q++];
}else{
int i = p, j = q;
for(;i < s.length && j < t.length;i++,j++){
if(s[i] < t[j]){
for(int k = p, o = k;k < i && s[k] == s[o];k++){
ret[r++] = s[p++];
}
continue outer;
}
if(s[i] > t[j]){
for(int k = q, o = k;k < j && t[k] == t[o];k++){
ret[r++] = t[q++];
}
continue outer;
}
}
if(i == s.length){
for(int k = q, o = k;k < j && t[k] == t[o];k++){
ret[r++] = t[q++];
}
continue outer;
}
if(j == t.length){
for(int k = p, o = k;k < i && s[k] == s[o];k++){
ret[r++] = s[p++];
}
continue outer;
}
throw new RuntimeException();
}
}
out.println(new String(ret));
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Morgan and a String HackerRank Solution
import io
def pick_smaller_char(s1, s2, idx1, idx2, len1, len2, i1, i2):
if(len1 <= idx1[0]):
idx2[0] += 1
return s2[idx2[0]-1]
if(len2 <= idx2[0]):
idx1[0] += 1
return s1[idx1[0]-1]
if(s1[idx1[0]] > s2[idx2[0]]):
idx2[0] += 1
return s2[idx2[0]-1]
elif(s1[idx1[0]] < s2[idx2[0]]):
idx1[0] +=1
return s1[idx1[0]-1]
else:
if(i1[0] < idx1[0] or i2[0] < idx2[0]):
i1[0] = idx1[0]
i2[0] = idx2[0]
else:
pass
while (i1[0] < len1) and (i2[0] < len2) and (s1[i1[0]] == s2[i2[0]]):
i1[0] += 1
i2[0] += 1
if((i1[0] < len1 and i2[0] < len2) and (s1[i1[0]] != s2[i2[0]])): #we found a tie breaker
if(s1[i1[0]] > s2[i2[0]]):
idx2[0] += 1
return s2[idx2[0]-1]
elif(s1[i1[0]] < s2[i2[0]]):
idx1[0] +=1
return s1[idx1[0]-1]
elif(i1[0] < len1 and i2[0] >= len2): #we ran out of s2 and it was all the same until
idx1[0] +=1
return s1[idx1[0]-1]
elif(i1[0] >= len1 and i2[0] < len2): #we ran out of s1 and it was all the same until
idx2[0] +=1
return s2[idx2[0]-1]
else: #everything is the same on both sides
i1[0] = 0
i2[0] = 0
if((len1 - idx1[0]) > (len2 - idx2[0])):
idx1[0] += 1
return s1[idx1[0]-1]
else:
idx2[0] += 1
return s2[idx2[0]-1]
def main():
trials = int(input())
for trial in range(trials):
word1 = input()
word2 = input()
word = io.StringIO()
len1 = len(word1)
len2 = len(word2)
idx1 = [0]
idx2 = [0]
i1 = [0]
i2 = [0]
timeout = 0
while ((len1 - idx1[0]) > 0) or ((len2 - idx2[0]) > 0):
word.write(pick_smaller_char(word1,word2,idx1,idx2,len1,len2,i1,i2))
print(word.getvalue())
word.close()
if __name__ == '__main__':
main()
Python 2 Morgan and a String HackerRank Solution
T = input()
for i in range(T):
J = raw_input()
D = raw_input()
J += "z"
D += "z"
j = 0
d = 0
S = ""
while j < len(J) and d < len(D):
if J[j:] < D[d:]:
S += J[j]
j += 1
else:
S += D[d]
d += 1
S = S[:-1]
if j < len(J):
S += J[j:-1]
if d < len(D):
S += D[d:-1]
print S
C Morgan and a String HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char str1[100001];
char str2[100001];
void printequal(int *i,int len1,int *j,int len2){
char c=str1[*i],ci,cj;
int i1,j1,k;
for(i1=*i,j1=*j;str1[i1]==str2[j1]&&i1<len1&&j1<len2;i1++,j1++){
if(str1[i1]>c){
for(;str1[*i]==c;(*i)++)
printf("%c",str1[*i]);
return;
}
}
if(i1==len1){
for(;str2[*j]==c;(*j)++)
printf("%c",str2[*j]);return;
}
else if(j1==len2){
for(;str1[*i]==c;(*i)++)
printf("%c",str1[*i]);return;
}
else if(str1[i1]<c && str1[i1]<str2[j1]){
for(;*i<i1;(*i)++)
printf("%c",str1[*i]);return;
}
else if(str2[j1]<c && str1[i1]>str2[j1]){
for(;*j<j1;(*j)++)
printf("%c",str2[*j]);return;
}
else{
for(;str1[*i]==c;(*i)++)
printf("%c",str1[*i]);
return;
}
return;
}
int main(){
int T,i,j,len1,len2;
scanf("%d",&T);
while(T--){
scanf("%s%s",str1,str2);
len1=strlen(str1);
len2=strlen(str2);
i=0;j=0;
while(i<len1 || j<len2){
if(i==len1){
printf("%c",str2[j]);j++;
}
else if(j==len2){
printf("%c",str1[i]);i++;
}
else if(str1[i]<str2[j]){
printf("%c",str1[i]);i++;
}
else if(str1[i]>str2[j]){
printf("%c",str2[j]);j++;
}
else{
printequal(&i,len1,&j,len2);
}
}
printf("\n");
}
return 0;
}
Comments 1