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 :



title-img 




                        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

2D Array-DS

Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t

View Solution →

Dynamic Array

Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.

View Solution →

Left Rotation

A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d

View Solution →

Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun

View Solution →

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →

Print the Elements of a Linked List

This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode

View Solution →