What is the time complexity of Design a Text Editor?

The optimal solution has a time complexity of O(k).

What data structures are used to solve Design a Text Editor?

This problem uses Linked List, String, Stack, Design, Simulation, Doubly-Linked List. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Design a Text Editor?

Insight 1: Using two lists (or stacks) `left` and `right` is a simple and effective way to represent the text editor's content with the cursor position implicitly defined by the boundary between these two lists. The left list contains characters to the left of the cursor, and the right list contains characters to the right of the cursor (in reverse order). Insight 2: The core operations (add, delete, move cursor) translate directly to pushing and popping elements from the appropriate list/stack. This allows for an O(k) solution where k is the number of characters to add, delete, or move the cursor.

Which companies ask LeetCode 2296. Design a Text Editor in interviews?

This problem is frequently asked at Block, Dropbox, Jane Street, Rubrik, Salesforce and 2 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Design a Text Editor - LeetCode 2296 Solution

Q: How to solve Design a Text Editor?

The solution uses two lists (or stacks conceptually) to represent the text: `left` and `right`. The `left` list stores the characters to the left of the cursor, and the `right` list stores the characters to the right of the cursor (in reverse order, so the last element added is the closest to the cursor). Each operation modifies these lists accordingly to simulate the text editor's behavior.

Design a Text Editor - Complete Solution Guide

Design a Text Editor is LeetCode problem 2296, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Design a text editor with a cursor that can do the following: Add text to where the cursor is. Delete text from where the cursor is (simulating the backspace key). Move the cursor either left or right. When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds. Implement the TextEditor class: TextEditor() Initial

Detailed Explanation

The problem requires designing a text editor that supports adding text, deleting text (backspace), and moving the cursor left and right. The text editor must maintain the current text and the cursor's position within that text. The cursor cannot move beyond the boundaries of the text. The `cursorLeft` and `cursorRight` methods should return the last 10 characters to the left of the cursor (or fewer if there are fewer than 10 characters to the left).

Solution Approach

The solution uses two lists (or stacks conceptually) to represent the text: `left` and `right`. The `left` list stores the characters to the left of the cursor, and the `right` list stores the characters to the right of the cursor (in reverse order, so the last element added is the closest to the cursor). Each operation modifies these lists accordingly to simulate the text editor's behavior.

Step-by-Step Algorithm

Step 1: Initialize two lists (or stacks) called `left` and `right` to store characters on either side of the cursor.
Step 2: `addText(text)`: Append the characters of the input `text` to the `left` list.
Step 3: `deleteText(k)`: Remove the last `k` characters from the `left` list, if possible. Stop removing characters when the `left` list is empty or `k` becomes zero. Return the number of characters actually deleted.
Step 4: `cursorLeft(k)`: Move the cursor `k` positions to the left. This means moving characters from the `left` list to the `right` list. Stop when the `left` list is empty or `k` becomes zero. After the move, return the last 10 characters in the `left` list (or fewer if there are fewer than 10 characters).
Step 5: `cursorRight(k)`: Move the cursor `k` positions to the right. This means moving characters from the `right` list to the `left` list. Stop when the `right` list is empty or `k` becomes zero. After the move, return the last 10 characters in the `left` list (or fewer if there are fewer than 10 characters).

Key Insights

Insight 1: Using two lists (or stacks) `left` and `right` is a simple and effective way to represent the text editor's content with the cursor position implicitly defined by the boundary between these two lists. The left list contains characters to the left of the cursor, and the right list contains characters to the right of the cursor (in reverse order).
Insight 2: The core operations (add, delete, move cursor) translate directly to pushing and popping elements from the appropriate list/stack. This allows for an O(k) solution where k is the number of characters to add, delete, or move the cursor.
Insight 3: When moving the cursor, remember that the cursor position is implicitly between the `left` and `right` lists. Moving the cursor left means moving characters from the `left` list to the `right` list, and vice versa.

Complexity Analysis

Time Complexity: O(k)

Space Complexity: O(n)

Topics

This problem involves: Linked List, String, Stack, Design, Simulation, Doubly-Linked List.

Companies

Asked at: Block, Dropbox, Jane Street, Rubrik, Salesforce, Shopify, Snap.

Design a Text Editor | LeetCode 2296

Hard

Linked List String Stack Design Simulation Doubly-Linked List

Time: O(k)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class TextEditor {

    private List<Character> left;
    private List<Character> right;

    public TextEditor() {
        this.left = new ArrayList<>();
        this.right = new ArrayList<>();
    }

    public void addText(String text) {
        for (char c : text.toCharArray()) {
            this.left.add(c);
        }
    }

    public int deleteText(int k) {
        int deleted_count = 0;
        while (k > 0 && !this.left.isEmpty()) {
            this.left.remove(this.left.size() - 1);
            deleted_count += 1;
            k -= 1;
        }
        return deleted_count;
    }

    public String cursorLeft(int k) {
        while (k > 0 && !this.left.isEmpty()) {
            this.right.add(this.left.remove(this.left.size() - 1));
            k -= 1;
        }

        int num_chars_to_show = Math.min(10, this.left.size());
        StringBuilder sb = new StringBuilder();
        for (int i = this.left.size() - num_chars_to_show; i < this.left.size(); i++) {
            sb.append(this.left.get(i));
        }
        return sb.toString();
    }

    public String cursorRight(int k) {
        while (k > 0 && !this.right.isEmpty()) {
            this.left.add(this.right.remove(this.right.size() - 1));
            k -= 1;
        }

        int num_chars_to_show = Math.min(10, this.left.size());
        StringBuilder sb = new StringBuilder();
        for (int i = this.left.size() - num_chars_to_show; i < this.left.size(); i++) {
            sb.append(this.left.get(i));
        }
        return sb.toString();
    }
}

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor obj = new TextEditor();
 * obj.addText(text);
 * int param_2 = obj.deleteText(k);
 * String param_3 = obj.cursorLeft(k);
 * String param_4 = obj.cursorRight(k);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2296: Design a Text Editor - Detailed explanation and solution approaches.

Topics

Linked List String Stack Design Simulation Doubly-Linked List

Companies

BlockDropboxJane StreetRubrikSalesforceShopifySnap

Stats

Difficulty:Hard

Languages:4

Companies:7

Problem #:2296

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize two lists (or stacks) called `left` and `right` to store characters on either side of the cursor.
2
Step 2: `addText(text)`: Append the characters of the input `text` to the `left` list.
3
Step 3: `deleteText(k)`: Remove the last `k` characters from the `left` list, if possible. Stop removing characters when the `left` list is empty or `k` becomes zero. Return the number of characters actually deleted.
4
Step 4: `cursorLeft(k)`: Move the cursor `k` positions to the left. This means moving characters from the `left` list to the `right` list. Stop when the `left` list is empty or `k` becomes zero. After the move, return the last 10 characters in the `left` list (or fewer if there are fewer than 10 characters).
5
Step 5: `cursorRight(k)`: Move the cursor `k` positions to the right. This means moving characters from the `right` list to the `left` list. Stop when the `right` list is empty or `k` becomes zero. After the move, return the last 10 characters in the `left` list (or fewer if there are fewer than 10 characters).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(k)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is linear with respect to `k` because the while loops in `deleteText`, `cursorLeft`, and `cursorRight` iterate up to `k` times. The space complexity is linear with respect to `n` because the maximum size of the `left` and `right` lists combined is proportional to the total number of characters added to the text editor.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Doubly Linked List

A doubly linked list can be used to represent the text, with each node storing a character. The cursor can be represented as a pointer to a node in the list. Adding text involves inserting new nodes, deleting text involves removing nodes, and moving the cursor involves updating the cursor pointer.

Time: O(k) for deleteText, cursorLeft, cursorRight, O(m) for addText where m is the length of added text.Space: O(n), where n is the number of characters.

Trade-offs: The doubly linked list approach might be slightly more complex to implement, but it could offer better performance for certain operations (e.g., inserting characters in the middle of the text using functions besides addText if such functionality were included), especially in scenarios with many insert operations.

String with Cursor Index

A single string can be used along with an integer to track cursor position. Adds are string inserts, deletes are string erases, and cursor movements simply adjust the index.

Time: O(n) for addText (string insert can take O(n) time), O(k) for deleteText, cursorLeft, cursorRight.Space: O(n), where n is the number of characters.

Trade-offs: Easier to implement, but the insert operation on standard strings can be expensive. Potentially slower than the two-list approach, particularly if there are numerous insertions and deletions.

✨

Key Insights

1Insight 1: Using two lists (or stacks) `left` and `right` is a simple and effective way to represent the text editor's content with the cursor position implicitly defined by the boundary between these two lists. The left list contains characters to the left of the cursor, and the right list contains characters to the right of the cursor (in reverse order).
2Insight 2: The core operations (add, delete, move cursor) translate directly to pushing and popping elements from the appropriate list/stack. This allows for an O(k) solution where k is the number of characters to add, delete, or move the cursor.
3Insight 3: When moving the cursor, remember that the cursor position is implicitly between the `left` and `right` lists. Moving the cursor left means moving characters from the `left` list to the `right` list, and vice versa.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: `deleteText(k)` when `k` is larger than the number of characters to the left of the cursor. The solution correctly deletes all characters to the left of the cursor and returns the number of characters actually deleted.
Edge case 2: `cursorLeft(k)` or `cursorRight(k)` when `k` is larger than the number of characters on either side of the cursor. The solution correctly moves the cursor as far as possible and stops at the boundary of the text.
Edge case 3: `cursorLeft(k)` or `cursorRight(k)` when the number of characters to the left of the cursor is less than 10. The solution correctly returns all available characters to the left.
Edge case 4: Adding an empty string using `addText("")`. The code should handle this gracefully, without crashing or producing unexpected results. The provided solution functions correctly for this case.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the boundary conditions of the cursor. For example, moving the cursor beyond the start or end of the text.

✗Common mistake 2: Failing to return the correct number of characters deleted in `deleteText`.

✗Common mistake 3: Inefficiently retrieving the last 10 characters in `cursorLeft` and `cursorRight`. Always remember to get `min(10, len(self.left))` instead of assuming `len(self.left)` is at least 10.

✗Common mistake 4: Forgetting that the 'right' list needs to have items added and removed from its end, effectively behaving like a stack. Failing to use `pop()` and `append()` consistently results in incorrect cursor behavior.

✗Common mistake 5: In the C implementation, failing to manage memory properly (allocating and freeing memory) which can lead to memory leaks.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Implementing text editors in software applications (e.g., word processors, code editors).

🏦Real-world scenario 2: Implementing command-line interfaces where users can edit commands before execution.

🎮Real-world scenario 3: Developing mobile keyboard auto-correction features, where cursor movements and deletions are fundamental operations.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Design a Text Editor"?

For this hard-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?