Given a string S, the task is to change the string if it doesn’t follow any of the rules given below and print the updated string. The rules for the proofreading are:
- If there are three consecutive characters, then it’s a wrong spell. Remove one of the characters. For Example string “ooops” can be changed to “oops”.
- If two pairs of the same characters (AABB) are connected together, it’s a wrong spell. Delete one of the characters of the second pair. For Example string “hello” can be changed to “hello”.
- The rules follow the priority from left to right.
Input: S = “hello”
Output: hello
Explanation:
As per the Rule #2
hello => hello
Input: S = “woooow”
Output: woow
Explanation:
As per the Rule #2
woooow => wooow
As per the Rule #1
wooow => woow
Approach: The idea is to traverse the string and if there is a wrong spelling, remove the extra characters according to the given conditions. As the priority of errors is from left to right, and according to the rules given, it can be seen that the judgement of spelling errors will not conflict. Consider traversing from left to right, adding the already legal characters to the result. Below are the steps:
- Initialize a stack to store the characters and to compare the last characters of the string.
- Traverse the string and add the character to the stack.
- Check the last 3 characters of the stack, if the same then pop the character at the top of the stack.
- Check the last 4 characters of the stack, if the same then pop the character at the top of the stack.
- Finally, return the characters of the stack.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
string proofreadSpell(string& str)
{
vector< char > result;
for ( char c : str) {
result.push_back(c);
int n = result.size();
if (n >= 3) {
if (result[n - 1]
== result[n - 2]
&& result[n - 1]
== result[n - 3]) {
result.pop_back();
}
}
n = result.size();
if (n >= 4) {
if (result[n - 1]
== result[n - 2]
&& result[n - 3]
== result[n - 4]) {
result.pop_back();
}
}
}
string resultStr = "" ;
for ( char c : result) {
resultStr += c;
}
return resultStr;
}
int main()
{
string str = "hello" ;
cout << proofreadSpell(str);
}
|
Java
import java.util.*;
class GFG{
public static String proofreadSpell(String str)
{
Vector<Character> result = new Vector<Character>();
for ( int i = 0 ; i < str.length(); i++)
{
result.add(str.charAt(i));
int n = result.size();
if (n >= 3 )
{
if (result.get(n - 1 ) ==
result.get(n - 2 ) &&
result.get(n - 1 ) ==
result.get(n - 3 ))
{
result.remove(result.size() - 1 );
}
}
n = result.size();
if (n >= 4 )
{
if (result.get(n - 1 ) ==
result.get(n - 2 ) &&
result.get(n - 3 ) ==
result.get(n - 4 ))
{
result.remove(result.size() - 1 );
}
}
}
String resultStr = "" ;
for (Character c : result)
{
resultStr += c;
}
return resultStr;
}
public static void main(String[] args)
{
String str = "hello" ;
System.out.println(proofreadSpell(str));
}
}
|
Python3
def proofreadSpell( str ):
result = []
for c in str :
result.append(c)
n = len (result)
if (n > = 3 ):
if (result[n - 1 ] = = result[n - 2 ] and
result[n - 1 ] = = result[n - 3 ]):
result.pop()
n = len (result)
if (n > = 4 ):
if (result[n - 1 ] = = result[n - 2 ] and
result[n - 3 ] = = result[n - 4 ]):
result.pop()
resultStr = ""
for c in result:
resultStr + = c
return resultStr
str = "hello"
print (proofreadSpell( str ))
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
static string proofreadSpell( string str)
{
List< char > result = new List< char >();
foreach ( char c in str)
{
result.Add(c);
int n = result.Count;
if (n >= 3)
{
if (result[n - 1] == result[n - 2] &&
result[n - 1] == result[n - 3])
{
result.RemoveAt(n - 1);
}
}
n = result.Count;
if (n >= 4)
{
if (result[n - 1] == result[n - 2] &&
result[n - 3] == result[n - 4])
{
result.RemoveAt(n - 1);
}
}
}
string resultStr = "" ;
foreach ( char c in result)
{
resultStr += c;
}
return resultStr;
}
public static void Main( string [] args)
{
string str = "hello" ;
Console.Write(proofreadSpell(str));
}
}
|
Javascript
<script>
function proofreadSpell(str)
{
var result = [];
str.split( '' ).forEach(c => {
result.push(c);
var n = result.length;
if (n >= 3) {
if (result[n - 1]
== result[n - 2]
&& result[n - 1]
== result[n - 3]) {
result.pop();
}
}
n = result.length;
if (n >= 4) {
if (result[n - 1]
== result[n - 2]
&& result[n - 3]
== result[n - 4]) {
result.pop();
}
}
});
var resultStr = "" ;
result.forEach(c => {
resultStr += c;
});
return resultStr;
}
var str = "hello" ;
document.write( proofreadSpell(str));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
- Initialize two pointers i and j to the start of the string.
- Traverse the string from left to right using the j pointer:
a. If the current character at j is the same as the character two positions to the left (i.e., j – 2), skip this character by incrementing j.
b. If the current character at j is the same as the character one position to the left (i.e., j – 1) and the character two positions to the left is the same as the character three positions to the left (i.e., i – 1), skip the current character by incrementing j.
c. Otherwise, add the current character to the result string and increment both i and j.
- Return the result string.
C++
#include <iostream>
#include <string>
using namespace std;
string proofreadSpell(string str)
{
int n = str.size();
string result = "" ;
int i = 0, j = 0;
while (j < n) {
if (j >= 2 && str[j] == str[j - 1]
&& str[j] == str[j - 2]) {
j++;
}
else if (j >= 3 && str[j] == str[j - 1]
&& str[j - 2] == str[j - 3]) {
j++;
}
else {
result += str[j];
i++;
j++;
}
}
return result;
}
int main()
{
string str = "hello" ;
cout << proofreadSpell(str) << endl;
return 0;
}
|
Java
public class ProofreadSpell {
public static String proofreadSpell(String str) {
int n = str.length();
StringBuilder result = new StringBuilder();
int i = 0 , j = 0 ;
while (j < n) {
if (j >= 2 && str.charAt(j) == str.charAt(j - 1 )
&& str.charAt(j) == str.charAt(j - 2 )) {
j++;
}
else if (j >= 3 && str.charAt(j) == str.charAt(j - 1 )
&& str.charAt(j - 2 ) == str.charAt(j - 3 )) {
j++;
} else {
result.append(str.charAt(j));
i++;
j++;
}
}
return result.toString();
}
public static void main(String[] args) {
String str = "hello" ;
System.out.println(proofreadSpell(str));
}
}
|
Python3
def proofread_spell( str ):
n = len ( str )
result = ""
i, j = 0 , 0
while j < n:
if j > = 2 and str [j] = = str [j - 1 ] and str [j] = = str [j - 2 ]:
j + = 1
elif j > = 3 and str [j] = = str [j - 1 ] and str [j - 2 ] = = str [j - 3 ]:
j + = 1
else :
result + = str [j]
i + = 1
j + = 1
return result
str = "hello"
print (proofread_spell( str ))
|
C#
using System;
class Program
{
static string ProofreadSpell( string str)
{
int n = str.Length;
string result = "" ;
int i = 0, j = 0;
while (j < n)
{
if (j >= 2 && str[j] == str[j - 1] && str[j] == str[j - 2])
{
j++;
}
else if (j >= 3 && str[j] == str[j - 1] && str[j - 2] == str[j - 3])
{
j++;
}
else
{
result += str[j];
i++;
j++;
}
}
return result;
}
static void Main()
{
string str = "hello" ;
string correctedStr = ProofreadSpell(str);
Console.WriteLine(correctedStr);
Console.ReadLine();
}
}
|
Javascript
function proofreadSpell(str) {
const n = str.length;
let result = '' ;
let i = 0, j = 0;
while (j < n)
{
if (j >= 2 && str[j] == str.charAt[j - 1] && str[j] == str[j - 2]) {
j++;
}
else if (j >= 3 && str[j] == str.charAt[j - 1] && str[j - 2] == str[j - 3]) {
j++;
} else {
result += str[j];
i++;
j++;
}
}
return result;
}
const str = "hello" ;
console.log(proofreadSpell(str));
|
Time Complexity: O(N)
Auxiliary Space: O(N)