Super Reduced String Hackerrank problem solution

Super Reduced String Hackerrank

Steve has a string, x, consisting of n lower case English alphabetic letters. In one operation, he can delete any pair of adjacent letters with the same value. For example, string “aabcc” would become either “aab” or “bcc” after the operation.

Statement:

Steve wants to reduce s as much as possible. To do this, he will repeat the above operation as many times as it can be performed. Help Steve out by finding and printing s‘s non-reducible form!

Note: If the final string is empty, print Empty String.

Input Format:- A single string, s.

Visit Problem at “https://www.hackerrank.com/challenges/reduced-string”

Constraints
1<=n<=100
Output Format:- If the final string is empty, print Empty String; otherwise, print the final non-reducible string.

Sample Input 0:- aaabccddd
Sample Output 0:- abd
Sample Case 0:- Steve can perform the following sequence of operations to get the final string:

aaabccddd → abccddd
abccddd → abddd
abddd → abd

Thus, we print abd.

Sample Input 1:- baab
Sample Output 1:- Empty String
Explanation 1:- Steve can perform the following sequence of operations to get the final string:

baab → bb
bb → Empty String

Thus, we print Empty String.

Sample Input 2:- aa
Sample Output 2:- Empty String
Explanation 2:- Steve can perform the following sequence of operations to get the final string:

aa → Empty String
Thus, we print Empty String.

Solution

In this problem, to get the fully reduced string, we have to use the stack. Suppose we are at the ith character of the string.Suppose we are at the ith position of the string. If the character at top of the stack is same as S[i], we pop the top element of the stack and move to i+1th position. Otherwise, if the stack is an empty or top element of the stack is not equal to S[i], we will push S[i] to the top of the stack and then move to i+1th position.

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

string s;
vector<int > st;

int main() {
  cin >> s;
  rep(i,0,s.size()) {
    if(!st.size() || s[st.back()] != s[i]) {
      st.push_back(i);
    } else {
      st.pop_back();
    }
  }
  if(!st.size()) {
    printf("Empty String\n");
  } else {
    rep(i,0,st.size()) {
      printf("%c",s[st[i]]);
    }
    printf("\n");
  }
  return 0;
}


Second II:-

 method : str.size() returns an (unsigned int). If you want to compare a signed int (int i) to an unsigned int (str.size()), you should use static_cast<> to tell the compiler to convert the unsigned int to an int before comparing.

More problems at “https://www.hackerrank.com/”

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    
    
    string str; cin >> str;
int i=0;

while(i < static_cast< int > (str.size()-1)) {
	if(i>-1 && str[i] == str[i+1]) {
		str.erase(i,2);
		i--;
	} else
		i++;
}
    
if(str.empty())
	cout << "Empty String" << endl;
else
	cout << str << endl;
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        scan.close();
        
        while (true) {
            // Used for loop termination
            int len = s.length();
            
            // "(.)" is a capturing group that captures any character
            // "\\1" is a backreference that will match the character captured by the first capturing group (i.e. the one captured by "(.)")
            s = s.replaceAll("(.)\\1", "");
            
            // If no changes were made to string, break loop
            if( s.length() == len ){
                break;
            }
        }

        System.out.println( (s.isEmpty()) ? "Empty String" : s);
    }
}


private static String solution(String s){
 if(s.length() <= 1) return s; 
for(int i = 1; i < s.length(); i ++){ 
if(s.charAt(i) == s.charAt(i-1))
{ 
return solution(s.substring(0, i-1) + s.substring(i+1)); } }
 return s; 
}
# Enter your code here. Read input from STDIN. Print output to STDOUT
s = raw_input()
ans = 1
assert len(s) >= 1 and len(s) <= 100000
for c in s:
    if ord(c) >= ord('A') and ord(c) <= ord('Z'):
        ans = ans + 1

print ans
 Python:
def removeRepeats(S):
    LS = list(S)
    i = 0 
    while i < len(LS)-1:
        if LS[i]==LS[i+1]:
            del LS[i]
            del LS[i]
            i = 0
            if len(LS) == 0:
                print 'Empty String'
                break
        else:
            i+=1
    return ''.join(LS)

 

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.