Long Pressed Name - Practice Coding Problems

Long Pressed Name - Problem

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return true if it is possible that it was your friend's name, with some characters (possibly none) being long pressed.

Input & Output

Example 1 — Basic Long Press

$ Input: name = "alex", typed = "aaleex"

› Output: true

💡 Note: The 'a' and 'e' were long pressed, resulting in extra characters, but the sequence matches the name

Example 2 — Wrong Character

$ Input: name = "saeed", typed = "ssaaedd"

› Output: false

💡 Note: The 'e' in typed was long pressed, but we're missing one 'e' that should appear after 'a'

Example 3 — Perfect Match

$ Input: name = "leelee", typed = "lleeelee"

› Output: true

💡 Note: All characters match with some long presses on 'l' and 'e'

Constraints

1 ≤ name.length ≤ 1000
1 ≤ typed.length ≤ 1000
name and typed consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Friend's name and what was actually typed

Process

Check if typed string could result from long-pressing keys

Output

Return true if typing is possible, false otherwise

Key Takeaway

🎯 Key Insight: Use two pointers to match characters while allowing repetitions from long-pressed keys

Asked in

G Google 15 f Facebook 12

The key insight is to use two pointers to traverse both strings simultaneously, allowing for long-pressed characters. Best approach uses two pointers technique. Time: O(n + m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers	O(n + m)	O(1)	Use two pointers to efficiently compare characters in both strings
Brute Force	O(2^n)	O(n)	Try all possible character matchings between name and typed

Two Pointers — Algorithm Steps

Step 1: Initialize two pointers at start of both strings
Step 2: Match current characters, advance both pointers
Step 3: If characters don't match but previous character in typed repeats, skip it
Step 4: Continue until both strings are fully processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set pointers at start of both strings

Match

Compare characters and advance pointers

Handle Repeats

Skip repeated characters in typed string

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* name, char* typed) {
    int i = 0, j = 0;
    int nameLen = strlen(name);
    int typedLen = strlen(typed);
    
    while (i < nameLen && j < typedLen) {
        if (name[i] == typed[j]) {
            i++;
            j++;
        } else if (j > 0 && typed[j] == typed[j-1]) {
            j++;
        } else {
            return false;
        }
    }
    
    // Check if we've matched all characters in name
    if (i < nameLen) {
        return false;
    }
    
    // Skip any remaining repeated characters in typed
    while (j < typedLen) {
        if (typed[j] == typed[j-1]) {
            j++;
        } else {
            return false;
        }
    }
    
    return true;
}

int main() {
    char name[1001], typed[1001];
    fgets(name, sizeof(name), stdin);
    fgets(typed, sizeof(typed), stdin);
    name[strcspn(name, "\n")] = 0;
    typed[strcspn(typed, "\n")] = 0;
    
    bool result = solution(name, typed);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through both strings where n and m are lengths of name and typed

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler