HackerEarth Exploring ruins problem solution

In this HackerEarth Exploring ruins problem solution, Little robot CJ-17 is exploring ancient ruins. He found a piece of paper with a word written on it. Fortunately, people who used to live at this location several thousand years ago used only two letters of the modern English alphabet: ‘a’ and ‘b’. It’s also known, that no ancient word contains two letters ‘a’ in a row. CJ-17 has already recognized some of the word letters, the others are still unknown.

CJ-17 wants to look up all valid words that could be written on this paper in an ancient dictionary. He needs your help. Find him the word, which is the first in alphabetical order and could be written on the paper.

HackerEarth Exploring ruins problem solution.

#include <cstdio>

int s[1234567];

int main() {
  int c = getchar();
  while (c <= 32) c = getchar();
  int n = 0;
  while (c > 32) {
    s[n++] = c;
    c = getchar();
  }
  for (int i = 0; i < n; i++) {
    if (s[i] != '?') continue;
    if ((i > 0 && s[i - 1] == 'a') || (i + 1 < n && s[i + 1] == 'a')) {
      s[i] = 'b';
    } else {
      s[i] = 'a';
    }
  }
  for (int i = 0; i < n; i++) putchar(s[i]);
  puts("");
}

Second solution

#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 norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-8
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

#define ldouble long double

using namespace std;

long long INF = 1e9;
const int N = 210031;

string st;
string ans;

bool valid()
{
    for (int i=0;i+1<st.size();i++)
    {
        if (st[i]=='a'&&st[i+1]=='a')
            return false;
    }
    return true;
}

void backtrack(int ps)
{
    if (!valid())
        return ;

    if (ans.size())
        return;
    if (ps==st.size())
    {
        if (valid())
        {
            ans=st;
        }
        return ;
    }
    if (st[ps]!='?')
    {
        backtrack(ps+1);
    }
    else
    {
        st[ps]='a';
        backtrack(ps+1);
        st[ps]='b';
        backtrack(ps+1);
        st[ps]='?';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin>>st;

    backtrack(0);

    cout<<ans<<endl;

    cin.get(); cin.get();
    return 0;
}

coding problems solutions