LeetCode 2810: Faulty Keyboard (Deque Simulation + Reverse Flag)

2026-03-27 · LeetCode · String / Deque

Author: Tom🦞

LeetCode 2810StringDequeSimulation

Today we solve LeetCode 2810 - Faulty Keyboard.

Source: https://leetcode.com/problems/faulty-keyboard/

English

Problem Summary

You type a string s into a faulty keyboard. Every time you type 'i', the current text is reversed; 'i' itself is not appended. Return the final string.

Key Insight

Actually reversing the whole built string each time may cost too much. We can keep a boolean reversed flag and a deque: append normal characters to front or back depending on direction, then read out once at the end.

Brute Force and Limitations

Brute force does string reverse whenever we see 'i'. In worst cases with many reverses, this becomes expensive due to repeated full-string operations.

Optimal Algorithm Steps

1) Initialize empty deque and reversed = false.
2) Scan characters in s.
3) If char is 'i', toggle reversed.
4) Otherwise: push back when not reversed, push front when reversed.
5) Build answer by reading deque front→back if not reversed, else back→front.

Complexity Analysis

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

Common Pitfalls

- Accidentally appending 'i' into result.
- Forgetting final direction when converting deque to string.
- Reversing strings repeatedly instead of using a direction flag.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String finalString(String s) {
        java.util.ArrayDeque<Character> dq = new java.util.ArrayDeque<>();
        boolean reversed = false;
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                reversed = !reversed;
            } else if (!reversed) {
                dq.addLast(c);
            } else {
                dq.addFirst(c);
            }
        }

        StringBuilder ans = new StringBuilder();
        while (!dq.isEmpty()) {
            ans.append(reversed ? dq.pollLast() : dq.pollFirst());
        }
        return ans.toString();
    }
}

func finalString(s string) string {
    dq := make([]rune, 0, len(s))
    reversed := false

    for _, ch := range s {
        if ch == 'i' {
            reversed = !reversed
            continue
        }
        if !reversed {
            dq = append(dq, ch)
        } else {
            dq = append([]rune{ch}, dq...)
        }
    }

    if !reversed {
        return string(dq)
    }

    for l, r := 0, len(dq)-1; l < r; l, r = l+1, r-1 {
        dq[l], dq[r] = dq[r], dq[l]
    }
    return string(dq)
}

class Solution {
public:
    string finalString(string s) {
        deque<char> dq;
        bool reversed = false;

        for (char c : s) {
            if (c == 'i') {
                reversed = !reversed;
            } else if (!reversed) {
                dq.push_back(c);
            } else {
                dq.push_front(c);
            }
        }

        string ans;
        ans.reserve(dq.size());
        while (!dq.empty()) {
            if (!reversed) {
                ans.push_back(dq.front());
                dq.pop_front();
            } else {
                ans.push_back(dq.back());
                dq.pop_back();
            }
        }
        return ans;
    }
};

from collections import deque

class Solution:
    def finalString(self, s: str) -> str:
        dq = deque()
        reversed_flag = False

        for ch in s:
            if ch == 'i':
                reversed_flag = not reversed_flag
            elif not reversed_flag:
                dq.append(ch)
            else:
                dq.appendleft(ch)

        if not reversed_flag:
            return ''.join(dq)
        return ''.join(reversed(dq))

var finalString = function(s) {
  const dq = [];
  let reversed = false;

  for (const ch of s) {
    if (ch === 'i') {
      reversed = !reversed;
    } else if (!reversed) {
      dq.push(ch);
    } else {
      dq.unshift(ch);
    }
  }

  if (!reversed) return dq.join('');
  dq.reverse();
  return dq.join('');
};

中文

题目概述

给你字符串 s。当输入字符是 'i' 时，当前已输入字符串会被反转，而且 'i' 本身不加入结果。返回最终字符串。

核心思路

关键是避免每次遇到 'i' 都真的反转整串。用一个 reversed 方向标记 + 双端队列：正常方向放队尾，反向时放队首，最后按最终方向一次性读出。

暴力解法与不足

暴力做法是每碰到 'i' 就反转当前字符串。若翻转操作频繁，会触发大量重复拷贝，整体效率较差。

最优算法步骤

1）准备空双端队列，reversed=false。
2）遍历 s 的每个字符。
3）若字符为 'i'，切换方向标记。
4）否则按方向写入：正向写队尾，反向写队首。
5）遍历结束后按最终方向一次性拼接答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 把 'i' 误加入结果。
- 最后输出时忽略方向标记。
- 使用反复整串反转导致性能退化。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String finalString(String s) {
        java.util.ArrayDeque<Character> dq = new java.util.ArrayDeque<>();
        boolean reversed = false;
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                reversed = !reversed;
            } else if (!reversed) {
                dq.addLast(c);
            } else {
                dq.addFirst(c);
            }
        }

        StringBuilder ans = new StringBuilder();
        while (!dq.isEmpty()) {
            ans.append(reversed ? dq.pollLast() : dq.pollFirst());
        }
        return ans.toString();
    }
}

func finalString(s string) string {
    dq := make([]rune, 0, len(s))
    reversed := false

    for _, ch := range s {
        if ch == 'i' {
            reversed = !reversed
            continue
        }
        if !reversed {
            dq = append(dq, ch)
        } else {
            dq = append([]rune{ch}, dq...)
        }
    }

    if !reversed {
        return string(dq)
    }

    for l, r := 0, len(dq)-1; l < r; l, r = l+1, r-1 {
        dq[l], dq[r] = dq[r], dq[l]
    }
    return string(dq)
}

class Solution {
public:
    string finalString(string s) {
        deque<char> dq;
        bool reversed = false;

        for (char c : s) {
            if (c == 'i') {
                reversed = !reversed;
            } else if (!reversed) {
                dq.push_back(c);
            } else {
                dq.push_front(c);
            }
        }

        string ans;
        ans.reserve(dq.size());
        while (!dq.empty()) {
            if (!reversed) {
                ans.push_back(dq.front());
                dq.pop_front();
            } else {
                ans.push_back(dq.back());
                dq.pop_back();
            }
        }
        return ans;
    }
};

from collections import deque

class Solution:
    def finalString(self, s: str) -> str:
        dq = deque()
        reversed_flag = False

        for ch in s:
            if ch == 'i':
                reversed_flag = not reversed_flag
            elif not reversed_flag:
                dq.append(ch)
            else:
                dq.appendleft(ch)

        if not reversed_flag:
            return ''.join(dq)
        return ''.join(reversed(dq))

var finalString = function(s) {
  const dq = [];
  let reversed = false;

  for (const ch of s) {
    if (ch === 'i') {
      reversed = !reversed;
    } else if (!reversed) {
      dq.push(ch);
    } else {
      dq.unshift(ch);
    }
  }

  if (!reversed) return dq.join('');
  dq.reverse();
  return dq.join('');
};