**Stuck Keyboard- Google Top Interview Questions**

### Problem Statement :

You are given two strings typed and target. You want to write target, but the keyboard is stuck so some characters may be written 1 or more times. Return whether it's possible that typed was meant to write target. Constraints n ≤ 100,000 where n is the length of typed m ≤ 100,000 where n is the length of s Example 1 Input typed = "aaabcccc" target = "abc" Output True Explanation Each of the "a", "b", and "c" were typed Example 2 Input typed = "abc" target = "ab" Output False Explanation "c" was not typed

### Solution :

` ````
Solution in C++ :
bool solve(string s, string t) {
int curr = 0;
for (int i = 0; i < t.size();) {
int j = i + 1;
while (j < t.size() && t[j] == t[i]) j++;
if (curr == s.size()) return false;
if (s[curr] != t[i]) return false;
int nextindex = curr;
while (nextindex < s.size() && s[nextindex] == s[curr]) nextindex++;
if (nextindex - curr < j - i) return false;
curr = nextindex;
i = j;
}
return curr == s.size();
}
```

` ````
Solution in Java :
import java.util.*;
class Solution {
public boolean solve(String s, String t) {
int k = 0;
for (int i = 0; i < s.length(); i++) {
if (k >= t.length() || s.charAt(i) != t.charAt(k)) {
return false;
}
int j = i;
int cnt1 = 0;
int cnt2 = 0;
while (j < s.length() && s.charAt(j) == s.charAt(i)) {
j++;
cnt1++;
}
i = j - 1;
j = k;
while (j < t.length() && t.charAt(j) == t.charAt(k)) {
j++;
cnt2++;
}
k = j;
if (cnt1 < cnt2)
return false;
}
if (k != t.length())
return false;
return true;
}
}
```

` ````
Solution in Python :
from itertools import groupby, zip_longest
class Solution:
def solve(self, typed, target):
return all(
x is not None and y is not None and x[0] == y[0] and len(list(x[1])) <= len(list(y[1]))
for (x, y) in zip_longest(groupby(target), groupby(typed))
)
```

## View More Similar Problems

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →