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

1. Initialize two counters, one for 'A' and one for 'L', to zero.
2. 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.
3. 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.