Determine validity after digit-constrained deletions
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You're given a string S of length n consisting only of '(' , ')' , and digits '0'–'9'. For every digit at index i with numeric value v:
(
1) you must delete exactly v parentheses that occur at indices strictly less than i;
(
2) a given parenthesis can be deleted at most once across all digits;
(
3) digits themselves are not deleted and should be ignored when checking validity. After choosing deletions for all digits, consider the sequence of remaining parentheses (ignoring digits). Return true if there exists at least one choice of deletions such that the remaining parentheses form a valid parentheses string, otherwise return false. Also describe an efficient algorithm, its time and space complexity, and optionally output one valid witness set of deletions if it exists.
Overview: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine validity after digit-constrained deletions states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Read the full Google Software Engineer interview experience this question came from
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution {
public:
vector>> memo;
bool solve(int i, int deleted, int balance, string& s) {
if (balance < 0)
return false;
if (i == s.size())
return balance == 0;
int &res = memo[i][deleted][balance];
if (res != -1)
return res;
char ch = s[i];
// Digit
if (isdigit(ch)) {
int required = ch - '0';
if (deleted != required)
return res = false;
return res = solve(i + 1, deleted, balance, s);
}
// Delete
bool del = solve(i + 1, deleted + 1, balance, s);
// Keep
bool keep = false;
if (ch == '(') {
keep = solve(i + 1, deleted, balance + 1, s);
}
else {
if (balance > 0)
keep = solve(i + 1, deleted, balance - 1, s);
}
return res = del || keep;
}
bool solution(string s) {
int n = s.size();
memo.assign(
n,
vector>(
n + 1,
vector(n + 1, -1)
)
);
return solve(0, 0, 0, s);
}
};
Answer by mojahidislam221
boolean solution(String s) {
int D = 0;
for (char c : s.toCharArray()) if (Character.isDigit(c)) D += c - '0';
Set> dp = new HashSet<>();
dp.add(List.of(0, 0)); // (deleted, balance)
int need = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
need += ch - '0';
final int req = need;
dp.removeIf(st -> st.get(0) < req); // prefix feasibility
if (dp.isEmpty()) return false;
continue;
}
Set> next = new HashSet<>();
for (List st : dp) {
int d = st.get(0), b = st.get(1);
if (d < D) next.add(List.of(d + 1, b)); // delete (cap at D)
if (ch == '(') next.add(List.of(d, b + 1)); // keep '('
else if (b > 0) next.add(List.of(d, b - 1)); // keep ')'
}
dp = next;
}
return dp.contains(List.of(D, 0));
}
public class Sollution3 {
boolean solution(String s){
int indOp = 0, indCl = 1;
Set> dp = new HashSet<>();
dp.add(List.of(0,0));
int n = s.length();
int open = 0;
int close = 0;
for(int i=0;i> next;
if(Character.isDigit(ch)) {
int num = ch - '0';
next = dp.stream().filter(a -> (a.get(indOp) + a.get(indCl)) == num).collect(Collectors.toSet());
continue;
}
next = new HashSet<>();
for(List ele: dp){
if(ch=='('){
open++;
next.add(List.of(ele.get(indOp)+1,ele.get(indCl)));
next.add(ele);
}else {
close++;
next.add(List.of(ele.get(indOp),ele.get(indCl)+1));
int count = open + close;
int actualOpen = open-ele.get(indOp);
int actualClose = close - ele.get(indCl); // fixed: was open - ...
if(actualOpen>=actualClose){
next.add(ele);
}
}
}
dp = next;
}
for(List ans: dp){
if(ans.get(indOp).