algoadvance

Leetcode 3110. Score of a String

Problem Statement

You are given a string s consisting only of characters a, b, and c. The function scoreOfString(s: String) -> int should return the score of the string, where the score is calculated as follows:

• Every character a has a score of 1.
• Every character b has a score of 2.
• Every character c has a score of 3.
• For every contiguous subsegment of identical characters, the score of the subsegment is multiplied by the length of the subsegment.

For example, the score of the string "aaabbc" is calculated as follows:

• "aaa" has a score of 1 * 3 = 3
• "bb" has a score of 2 * 2 = 4
• "c" has a score of 3 * 1 = 3 So, the total score of "aaabbc" is 3 + 4 + 3 = 10.

Clarifying Questions

1. Input Constraints:
   • Minimum length of s?
   • Maximum length of s?
   • Any character other than a, b, and c that we might need to handle?
2. Examples:
   • Should consider empty string as input as well? How to handle?
   • Any case sensitivity rules?

Code

public class Solution {
    public int scoreOfString(String s) {
        if (s == null || s.length() == 0) return 0;

        int totalScore = 0;
        int currentScore = 0;
        int currentCount = 0;
        char prevChar = s.charAt(0);
        
        for (char c : s.toCharArray()) {
            if (c == prevChar) {
                currentCount++;
            } else {
                // Calculate the score of the previous contiguous segment
                totalScore += calculateSegmentScore(prevChar, currentCount);
                // Reset for the new character segment
                prevChar = c;
                currentCount = 1;
            }
        }
        
        // Handle the last segment
        totalScore += calculateSegmentScore(prevChar, currentCount);
        
        return totalScore;
    }

    private int calculateSegmentScore(char c, int count) {
        int baseScore = 0;
        switch (c) {
            case 'a':
                baseScore = 1;
                break;
            case 'b':
                baseScore = 2;
                break;
            case 'c':
                baseScore = 3;
                break;
        }
        return baseScore * count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.scoreOfString("aaabbc")); // Output: 10
        System.out.println(sol.scoreOfString("abcabc")); // Output: 9
        System.out.println(sol.scoreOfString(""));       // Output: 0
        System.out.println(sol.scoreOfString("aaa"));    // Output: 3
    }
}

Strategy

1. Initialization:
   • Start with setting the totalScore to 0.
   • Initialize currentScore and currentCount to 0.
   • Track the prevChar as the first character of the string s.
2. Traversing the String:
   • Iterate through each character c in the string s.
   • If the character c is the same as prevChar, increment currentCount.
   • If the character c is different from prevChar:
     • Calculate the score of the segment ending with prevChar and add it to totalScore.
     • Update prevChar to the new character c.
     • Reset currentCount to 1.
3. Final Segment Calculation:
   • After the loop, handle the last segment by adding its score to the totalScore.
4. Helper Function:
   • Implement calculateSegmentScore to calculate the score for a segment of identical characters based on the character’s base score.

Time Complexity

• Time Complexity: O(n), where n is the length of the input string s. We traverse the string once and perform constant-time operations.
• Space Complexity: O(1), since we’re using a fixed amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?