I like to read this solution as a small machine: keep the useful information, throw away the noise. For 925. Long Pressed Name, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isLongPressedName.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N+T)O(N+T), where N, TN,T are the lengths of name and typed.
- Space: O(N+T)O(N+T).
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Long Pressed Name.
02//Memory Usage: 8.4 MB, less than 98.25% of C++ online submissions for Long Pressed Name.
03
04class Solution {
05public:
06 bool isLongPressedName(string name, string typed) {
07 int cur = 0;
08 char last = typed[0];
09
10 for(char c : name){
11 char typedc = typed[cur++];
12 //ignore the redundant char
13 while(typedc != c && typedc == last){
14 typedc = typed[cur++];
15 }
16 // cout << c << " " << typedc << " " << last << endl;
17 //if(typedc != c && typedc != last), then it must be wrong
18 if(typedc != c && typedc != last) return false;
19 //if(typedc == c), it matches
20 last = typedc;
21 }
22 return true;
23 }
24};
25
26/**
27Approach 1: Group into Blocks
28**/
29
30/**
31Complexity Analysis
32
33Time Complexity: O(N+T)O(N+T), where N, TN,T are the lengths of name and typed.
34
35Space Complexity: O(N+T)O(N+T).
36**/
37
38/**
39class Group{
40public:
41 string key;
42 vector<int> count;
43 Group(string k, vector<int> c){
44 key = k;
45 count = c;
46 }
47};
48
49class Solution {
50public:
51 Group groupify(string s){
52 string key;
53 vector<int> count;
54 int anchor = 0;
55 int N = s.size();
56 for(int i = 0; i < N; i++){
57 if(i == N-1 || s[i] != s[i+1]){
58 key += s[i];
59 count.push_back(i - anchor + 1);
60 anchor = i+1;
61 }
62 }
63 return Group(key, count);
64 }
65 bool isLongPressedName(string name, string typed) {
66 Group g1 = groupify(name);
67 Group g2 = groupify(typed);
68 if(g1.key != g2.key) return false;
69
70 for(int i = 0; i < g1.count.size(); i++){
71 if(g2.count[i] < g1.count[i]) return false;
72 }
73 return true;
74 }
75};
76**/
77
78/**
79Approach 2: Two Pointer
80Intuition
81
82As in Approach 1, we want to check the key and the count. We can do this on the fly.
83
84Suppose we read through the characters name, and eventually it doesn't match typed.
85
86There are some cases for when we are allowed to skip characters of typed. Let's use a tuple to denote the case (name, typed):
87
88In a case like ('aab', 'aaaaab'), we can skip the 3rd, 4th, and 5th 'a' in typed because we have already processed an 'a' in this block.
89
90In a case like ('a', 'b'), we can't skip the 1st 'b' in typed because we haven't processed anything in the current block yet.
91
92Algorithm
93
94This leads to the following algorithm:
95
96For each character in name, if there's a mismatch with the next character in typed:
97If it's the first character of the block in typed, the answer is False.
98Else, discard all similar characers of typed coming up. The next (different) character coming must match.
99Also, we'll keep track on the side of whether we are at the first character of the block.
100**/
101
102/**
103
104Complexity Analysis
105
106Time Complexity: O(N+T)O(N+T), where N, TN,T are the lengths of name and typed.
107
108Space Complexity: O(1)O(1) in additional space complexity. (In Java, .toCharArray makes this O(N)O(N), but this can be easily remedied.)
109**/
110
111//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Long Pressed Name.
112//Memory Usage: 8.2 MB, less than 100.00% of C++ online submissions for Long Pressed Name.
113
114/**
115class Solution {
116public:
117 bool isLongPressedName(string name, string typed) {
118 int j = 0;
119 for(char c : name){
120 //run through typed, but still visiting name
121 if(j == typed.size()) return false;
122
123 if(typed[j] != c){
124 //0th char must match
125 //or not equal to the last char
126 if(j == 0 || typed[j] != typed[j-1]) return false;
127
128 char cur = typed[j];
129 //ignore all redundant chars
130 while(j < typed.size() && typed[j] == cur) j++;
131
132 //typed[j] is the char just behind all redundant chars
133 //if j is invalid, return false
134 //or if typed[j] is not equal to c, return false
135 if(j == typed.size() || typed[j] != c) return false;
136 }
137
138 //go to next char
139 j++;
140 }
141
142 return true;
143 }
144};
145**/Cost
Complexity
Time
O(N+T)O(N+T), where N, TN,T are the lengths of name and typed.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(N+T)O(N+T).
Auxiliary state plus the answer structure where the problem requires one.