2810. Faulty Keyboard - Solution & Explanation

Q: Is Faulty Keyboard easy or hard?

Faulty Keyboard is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The challenge is recognizing that repeated string reversals are inefficient and replacing them with a direction-based simulation.

Q: Faulty Keyboard Python/Java solution

In Python, a deque from the collections module works well for inserting characters at both ends. In Java, you can use a StringBuilder with a direction flag or a Deque . Both implementations follow the same O(n) simulation strategy.

The problem

Your laptop keyboard is faulty, and whenever you type a character 'i' on it, it reverses the string that you have written. Typing other characters works as expected.

You are given a 0-indexed string s, and you type each character of s using your faulty keyboard.

Return the final string that will be present on your laptop screen.

Example 1:

Input: s = "string"
Output: "rtsng"
Explanation: 
After typing first character, the text on the screen is "s".
After the second character, the text is "st". 
After the third character, the text is "str".
Since the fourth character is an 'i', the text gets reversed and becomes "rts".
After the fifth character, the text is "rtsn". 
After the sixth character, the text is "rtsng". 
Therefore, we return "rtsng".

Example 2:

Input: s = "poiinter"
Output: "ponter"
Explanation: 
After the first character, the text on the screen is "p".
After the second character, the text is "po". 
Since the third character you type is an 'i', the text gets reversed and becomes "op". 
Since the fourth character you type is an 'i', the text gets reversed and becomes "po".
After the fifth character, the text is "pon".
After the sixth character, the text is "pont". 
After the seventh character, the text is "ponte". 
After the eighth character, the text is "ponter". 
Therefore, we return "ponter".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.
s[0] != 'i'

Approach overview

Problem Overview: You type characters on a keyboard, but the key 'i' is faulty. Instead of being added to the text, it reverses the string typed so far. Given the input string s, simulate the typing process and return the final string.

Approach 1: Stack-Based Simulation (O(n^2) time, O(n) space)

Use a stack or dynamic string buffer to simulate typing. Iterate through the characters of s. For normal characters, push them onto the stack. When you encounter 'i', reverse the current stack contents. Reversal requires popping elements and rebuilding the sequence, which can take O(k) time where k is the current length. In the worst case—multiple 'i' operations—the repeated reversals push the total time to O(n^2). This approach mirrors the problem statement directly and is easy to reason about during an interview.

Approach 2: Two-Pointer / Direction Simulation (O(n) time, O(n) space)

A more efficient simulation avoids physically reversing the string each time. Maintain a direction flag that represents whether the current text is being built normally or reversed. Use a deque-like structure or two-pointer placement strategy: append characters to the back when the direction is normal and to the front when the direction is reversed. When you see 'i', simply toggle the direction flag instead of reversing the data. After processing the entire string, output the characters in the correct order based on the final direction. Each character is inserted exactly once, giving O(n) time complexity with O(n) space.

This problem is primarily about careful simulation of operations on a string. The optimized solution relies on controlling the insertion direction rather than repeatedly reversing the entire sequence.

Recommended for interviews: Start with the stack simulation because it clearly models the faulty keyboard behavior. Then optimize by eliminating repeated reversals using the two-pointer or deque strategy. Interviewers typically expect the O(n) simulation because it demonstrates awareness of hidden costs in repeated string reversals.

Approach 1: Stack-Based Approach

Utilize a stack data structure to manage the characters. When encountering 'i', reverse the current stack list.

Python

def process_string(s: str) -> str:
    result = []
    for char in s:
        if char == 'i':
            result.reverse()
        else:
            result.append(char)
    return ''.join(result)

s = "poiinter"
print(process_string(s))

Java

import java.util.Stack;

public class FaultyKeyboard {
    public static String processString(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                result.reverse();
            } else {
                result.append(c);
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String s = "poiinter";
        System.out.println(processString(s));
    }
}

C++

#include <iostream>
#include <string>
#include <algorithm>

std::string processString(const std::string &s) {
    std::string result;
    for (char c : s) {
        if (c == 'i') {
            std::reverse(result.begin(), result.end());
        } else {
            result.push_back(c);
        }
    }
    return result;
}

int main() {
    std::string s = "poiinter";
    std::cout << processString(s) << std::endl;
    return 0;
}

JavaScript

function processString(s) {
    let result = [];
    for (let char of s) {
        if (char === 'i') {
            result.reverse();
        } else {
            result.push(char);
        }
    }
    return result.join('');
}

let s = "poiinter";
console.log(processString(s));

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

void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(char *str, int len) {
    int i;
    for(i = 0; i < len / 2; i++) {
        swap(&str[i], &str[len - i - 1]);
    }
}

char* processString(char *s) {
    static char result[101];
    int index = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == 'i') {
            reverse(result, index);
        } else {
            result[index++] = s[i];
        }
    }
    result[index] = '\0';
    return result;
}

int main() {
    char s[] = "poiinter";
    printf("%s\n", processString(s));
    return 0;
}

using System;
using System.Text;

class Program {
    public static string ProcessString(string s) {
        StringBuilder result = new StringBuilder();
        foreach (char c in s) {
            if (c == 'i') {
                char[] charArray = result.ToString().ToCharArray();
                Array.Reverse(charArray);
                result = new StringBuilder(new string(charArray));
            } else {
                result.Append(c);
            }
        }
        return result.ToString();
    }

    static void Main() {
        string s = "poiinter";
        Console.WriteLine(ProcessString(s));
    }
}

The Python solution uses a list to gather characters. Encountering 'i' reverses the list using its reverse() method. Final conversion to string is done with join().

Complexity

Time Complexity: O(n^2); Space Complexity: O(n).

Try this approach in the editor

Approach 2: Two-Pointer Approach

Avoid string reversing by cleverly tracking the insertion position using a two-pointer technique, diving into the array-based manipulation.

Python

def process_two_pointer(s: str) -> str:
    result = [''] * len(s)
    left, right = 0, 0
    direction = 1
    for char in s:
        if char == 'i':
            direction = -direction
            left, right = right, left
        else:
            if direction == 1:
                result[right] = char
                right += 1
            else:
                left -= 1
                result[left] = char
    return ''.join(result[:right])

s = "poiinter"
print(process_two_pointer(s))

Java

public class FaultyKeyboard {
    public static String processTwoPointer(String s) {
        char[] result = new char[s.length()];
        int left = 0, right = 0;
        int direction = 1;
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                direction = -direction;
                int temp = left;
                left = right;
                right = temp;
            } else {
                if (direction == 1) {
                    result[right++] = c;
                } else {
                    result[--left] = c;
                }
            }
        }
        return new String(result, 0, right);
    }

    public static void main(String[] args) {
        String s = "poiinter";
        System.out.println(processTwoPointer(s));
    }
}

C++

#include <iostream>
#include <string>

std::string processTwoPointer(const std::string &s) {
    std::string result(s.size(), ' ');
    int left = 0, right = 0;
    int direction = 1;
    for (char c : s) {
        if (c == 'i') {
            direction = -direction;
            std::swap(left, right);
        } else {
            if (direction == 1) {
                result[right++] = c;
            } else {
                result[--left] = c;
            }
        }
    }
    return result.substr(0, right);
}

int main() {
    std::string s = "poiinter";
    std::cout << processTwoPointer(s) << std::endl;
    return 0;
}

JavaScript

function processTwoPointer(s) {
    let result = new Array(s.length);
    let left = 0, right = 0;
    let direction = 1;
    for (let char of s) {
        if (char === 'i') {
            direction = -direction;
            [left, right] = [right, left];
        } else {
            if (direction === 1) {
                result[right++] = char;
            } else {
                result[--left] = char;
            }
        }
    }
    return result.slice(0, right).join('');
}

let s = "poiinter";
console.log(processTwoPointer(s));

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

char* processTwoPointer(char *s) {
    static char result[101];
    int left = 0, right = 0;
    int direction = 1;
    for (int i = 0; s[i]; i++) {
        if (s[i] == 'i') {
            direction = -direction;
            int temp = left;
            left = right;
            right = temp;
        } else {
            if (direction == 1) {
                result[right++] = s[i];
            } else {
                result[--left] = s[i];
            }
        }
    }
    result[right] = '\0';
    return result;
}

int main() {
    char s[] = "poiinter";
    printf("%s\n", processTwoPointer(s));
    return 0;
}

using System;

class Program {
    public static string ProcessTwoPointer(string s) {
        char[] result = new char[s.Length];
        int left = 0, right = 0;
        int direction = 1;
        foreach (char c in s) {
            if (c == 'i') {
                direction = -direction;
                int temp = left;
                left = right;
                right = temp;
            } else {
                if (direction == 1) {
                    result[right++] = c;
                } else {
                    result[--left] = c;
                }
            }
        }
        return new string(result, 0, right);
    }

    static void Main() {
        string s = "poiinter";
        Console.WriteLine(ProcessTwoPointer(s));
    }
}

In Python, the solution employs array manipulation to manage each character based on a dynamically changing pointer logic. This avoids explicit reversals, enhancing efficiency.

Complexity

Time Complexity: O(n); Space Complexity: O(n).

Try this approach in the editor

Approach 3: Simulation

We directly simulate the keyboard input process, using a character array t to record the text on the screen, initially t is empty.

For each character c in string s, if c is not the character 'i', then we add c to the end of t; otherwise, we reverse all characters in t.

The final answer is the string composed of characters in t.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of string s.

TypeScript

function finalString(s: string): string {
    const t: string[] = [];
    for (const c of s) {
        if (c === 'i') {
            t.reverse();
        } else {
            t.push(c);
        }
    }
    return t.join('');
}

func finalString(s string) string {
	t := []rune{}
	for _, c := range s {
		if c == 'i' {
			for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
				t[i], t[j] = t[j], t[i]
			}
		} else {
			t = append(t, c)
		}
	}
	return string(t)
}

Rust

impl Solution {
    pub fn final_string(s: String) -> String {
        let mut t = Vec::new();
        for c in s.chars() {
            if c == 'i' {
                t.reverse();
            } else {
                t.push(c);
            }
        }
        t.into_iter().collect()
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Stack-Based Approach	Time Complexity: O(n^2); Space Complexity: O(n).
Two-Pointer Approach	Time Complexity: O(n); Space Complexity: O(n).
Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Stack-Based Simulation	O(n^2)	O(n)	Straightforward implementation when demonstrating the problem’s mechanics step by step
Two-Pointer / Direction Simulation	O(n)	O(n)	Preferred approach for interviews and production due to avoiding repeated reversals

Frequently asked questions

Is Faulty Keyboard easy or hard?

Faulty Keyboard is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The challenge is recognizing that repeated string reversals are inefficient and replacing them with a direction-based simulation.

Faulty Keyboard Python/Java solution

In Python, a deque from the collections module works well for inserting characters at both ends. In Java, you can use a StringBuilder with a direction flag or a Deque<Character>. Both implementations follow the same O(n) simulation strategy.

How to solve Faulty Keyboard in O(n)?

Iterate through the string while maintaining a direction flag. When encountering 'i', toggle the direction instead of reversing the current text. For other characters, append them to the front or back depending on the direction. This avoids repeated reversals and keeps the algorithm linear.

What is the best approach for Faulty Keyboard?

The most efficient approach uses direction simulation with a deque or two-pointer insertion strategy. Instead of reversing the string every time 'i' appears, toggle a direction flag and insert characters at the front or back accordingly. This keeps the complexity at O(n) time and O(n) space.

Is Faulty Keyboard asked at Google/Amazon/Meta?

The problem represents a common interview pattern focused on string simulation and efficient handling of reversals. Variants of this question appear in coding interviews at large tech companies where candidates are expected to optimize naive string operations to O(n).

What data structure is used in Faulty Keyboard?

Common implementations use a stack, dynamic string buffer, or a deque. The optimal solution typically uses a deque because it allows constant-time insertion at both the front and the back while simulating direction changes.

What is the time complexity of Faulty Keyboard?

The optimal solution runs in O(n) time because each character from the input string is processed once and inserted into the result exactly once. A naive stack-based simulation that physically reverses the string on every 'i' can degrade to O(n^2) time in the worst case.

Faulty Keyboard solution and explanation

The problem

Approach overview

Approach 1: Stack-Based Approach

Approach 2: Two-Pointer Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Faulty Keyboard solution and explanation

The problem

Approach overview

Approach 1: Stack-Based Approach

Approach 2: Two-Pointer Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems