Leetcode 551. Student Attendance Record I
Problem Explanation
The problem is asking to return whether the given string is qualified for reward or not. The string represents the attendance record of a student at school and contains characters only from (A-P-L).
'A': denotes absence, 'L': continuous late, 'P': Present or on time.
The reward qualification rules are: the record should have at most one 'A' (absence) and should not have more than two continuous 'L's (late). If the record violates any of these rules, we return False, implying the student cannot be rewarded for his attendance.
Walkthrough
Given a string, "PPALLP", iterate through the string checking each character. If the character is 'A', increase the count for 'A'. If it exceeds 1, return False because the rule for max of one 'A' was violated. If the character is 'L', increase the count for 'L'. If it exceeds 2, return False because the rule for max of two continuous 'L's was violated. If the character is not 'L', reset the 'L' counter to zero because 'L' count considers only continuous 'L's. If 'A' and continuous 'L' counters do not exceed their maximum threshold, return True to indicate the student qualified for reward.
Approach
The approach is straightforward. We use a single pass through the string while keeping track of 'A' count and continuous 'L' counts. We use two separate counters, one for 'A' and one for 'L'. As soon as a counter violates its rule, we immediately return False.
Algorithm Steps
- Initialize two counters, one for 'A' and one for 'L', to zero.
- Iterate each character in the string.
- If character is 'A', increase 'A' counter. If 'A' counter > 1, return False.
- If character is 'L', increase 'L' counter. If 'L' counter > 2, return False.
- If character is not 'L', reset 'L' counter to zero.
- If we finished the pass without violations, return True, indicating a qualified record.
Let's illustrate this through an example. We are given string "PPALLP": Iteration 1: first character is 'P'. Both 'A' and 'L' counters remain 0. Iteration 2: second 'P'. Still 'A' and 'L' counters are 0. Iteration 3: 'A' appears. 'A' counter increments to 1. Iteration 4: 'L' appears. 'L' counter increments to 1. Iteration 5: second 'L'. 'L' counter increments to 2. Iteration 6: 'P' appears. 'L' counter resets to 0. We completed iterations without any counter violation. Hence, return True.
Python Solution
1 2python 3class Solution: 4 def checkRecord(self, s: str) -> bool: 5 countA = 0 6 countL = 0 7 8 for c in s: 9 if c == 'A': 10 countA += 1 11 if countA > 1: 12 return False 13 if c != 'L': 14 countL = 0 15 elif c == 'L': 16 countL += 1 17 if countL > 2: 18 return False 19 20 # All rules are satisfied 21 return True
Java Solution
1
2java
3class Solution {
4 public boolean checkRecord(String s) {
5 int countA = 0;
6 int countL = 0;
7
8 for (char c : s.toCharArray()) {
9 if (c == 'A') {
10 countA++;
11 if (countA > 1)
12 return false;
13 }
14 if (c != 'L') {
15 countL = 0;
16 } else if (c == 'L') {
17 countL++;
18 if (countL > 2)
19 return false;
20 }
21 }
22
23 // All rules are satisfied
24 return true;
25 }
26}
JavaScript Solution
1 2javascript 3class Solution { 4 checkRecord (s) { 5 let countA = 0; 6 let countL = 0; 7 8 for (let c of s) { 9 if (c === 'A') { 10 countA++; 11 if (countA > 1) 12 return false; 13 } 14 if (c !== 'L') { 15 countL = 0; 16 } else if (c === 'L') { 17 countL++; 18 if (countL > 2) 19 return false; 20 } 21 } 22 23 // All rules are satisfied 24 return true; 25 } 26};
C++ Solution
1 2C++ 3class Solution { 4public: 5 bool checkRecord(string s) { 6 int countA = 0; 7 int countL = 0; 8 9 for (char c : s) { 10 if (c == 'A') { 11 countA++; 12 if (countA > 1) 13 return false; 14 } 15 if (c != 'L') { 16 countL = 0; 17 } else if (c == 'L') { 18 countL++; 19 if (countL > 2) 20 return false; 21 } 22 } 23 24 // All rules satisfied 25 return true; 26 } 27};
C# Solution
1
2C#
3public class Solution {
4 public bool CheckRecord(string s) {
5 int countA=0, countL=0;
6
7 foreach(char c in s) {
8 if(c == 'A') {
9 countA++;
10 if(countA > 1)
11 return false;
12 }
13 if(c != 'L') {
14 countL = 0;
15 } else {
16 countL++;
17 if (countL > 2)
18 return false;
19 }
20 }
21
22 // All rules satisfied
23 return true;
24 }
25}
During the iteration, if we meet "A", we increase the countA. If the countA is more than 1, return False. If we meet "L", we increase the countL, if the countL is more than 2, return False. Otherwise, if we meet "P", reset the countL.# Time and Space Complexity
The time complexity for this problem is O(n), where n is the length of the string. This is because we are iterating through the string only once. The space complexity, on the other hand, is O(1) as we are using a constant amount space to store our 'A' and 'L' counts, regardless of the input size.
Conclusion
We learned how to solve this problem using iteration and counting. The problem required us to consider counting in two different ways: one for any occurrence (for 'A') and the other for continuous occurrence (for 'L'). This is a common pattern that might be applied in other situations, especially when parsing a string or array.
The solutions provided in this article use languages most commonly used in coding interviews (Python, Java, JavaScript), along with C++ and C#. The logic remains the same across all languagesโonly the syntax changes. Remember to fully understand the logic before trying to remember or write the code.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.