Programming Exercises Documentation Help

June 2024, Week 1: June 1st - June 2nd

June 1 -> 3110. Score of a String

You are given a string s. The score of a string is defined as the sum of the absolute difference between the ASCII values of adjacent characters.

Return the score of s.

Example 1:

  • Input: s = "hello"

  • Output: 13

  • Explanation:

    • The ASCII values of the characters in s are: 'h' = 104, 'e' = 101, 'l' = 108, 'o' = 111. So, the score of s would be |104 - 101| + |101 - 108| + |108 - 108| + |108 - 111| = 3 + 7 + 0 + 3 = 13.

Example 2:

  • Input: s = "zaz"

  • Output: 50

  • Explanation:

    • The ASCII values of the characters in s are: 'z' = 122, 'a' = 97. So, the score of s would be |122 - 97| + |97 - 122| = 25 + 25 = 50.

Constraints:

  • 2 <= s.length <= 100

  • s consists only of lowercase English letters.

Approach 1: Linear Iteration with ASCII Value Comparison

def scoreOfString(s: str) -> int: """ Calculates the total score of a string based on absolute differences between adjacent character ASCII values. This function iterates through each pair of adjacent characters in the string, calculates the absolute difference between their ASCII values, and accumulates this into a total score. The time complexity of this function is O(n), where `n` is the length of the string. This is because it performs a single iteration over the string's characters. The space complexity is O(1) as it uses a constant amount of extra space to store variables. """ n = len(s) total_score = 0 for index in range(n - 1): total_score += abs((ord(s[index]) - ord(s[index + 1]))) # Alternatively, you can use pairwise from itertools to get the pairs of # adjacent characters s -> (s0, s1), (s1, s2), (s2, s3), ... # This alternative approach would have similar time and space # complexities, but offers a more concise way of generating pairs return total_score

Understanding the Core Idea

The central concept of this solution is to leverage ASCII value comparisons and linear iteration to calculate the score of the string. The solution exploits the fact that characters can be converted to their ASCII values, allowing for numerical comparisons.

  • ASCII Value Conversion: The solution uses the ord() function to convert characters to their ASCII values, enabling numerical operations.

  • Adjacent Character Comparison: By iterating through the string, the solution compares each character with its adjacent neighbor, calculating the absolute difference between their ASCII values.

  • Cumulative Scoring: The solution accumulates these differences into a total score, representing the overall " distance" between adjacent characters in the ASCII table.

Code Walkthrough

  1. Initialization:

    n = len(s) total_score = 0

    Here, we initialize two key variables:

    • n: Stores the length of the input string for efficient access later.

    • total_score: Initializes the accumulator for the string's score.

  2. Main Iteration and Score Calculation:

    for index in range(n - 1): total_score += abs((ord(s[index]) - ord(s[index + 1])))

    This is the core of the algorithm:

    • The loop iterates n-1 times, as we're comparing pairs of adjacent characters.

    • For each pair, we:

      1. Convert both characters to their ASCII values using ord().

      2. Calculate the difference between these ASCII values.

      3. Take the absolute value of this difference using abs().

      4. Add this value to the total_score.

  3. Result Return:

    return total_score

    After the iteration is complete, the function returns the accumulated total_score, which represents the final score of the string according to the problem's definition.

Complexity Analysis

Time Complexity:

  • , where is the length of the input string s. This is because the algorithm performs a single pass through the string, processing each character exactly once (except the last character, which is only used in the final comparison).

Space Complexity:

  • , or constant space. The algorithm uses a fixed amount of additional space regardless of the input size. It only requires a few variables (n, total_score, and index) to perform its calculations, and these do not scale with the input size.

Example

Input:

s = "hello"

Step-by-Step Walkthrough:

  1. Initialization:

    • The function receives the input string s = 'hello'.

    • The length of the string, n, is calculated as 5.

    • The total_score variable is initialized to 0.

  2. Main Loop (Calculating Character Pair Scores):

    • Iteration 1:

      • index = 0 (first character 'h')

      • char1 = 'h', char2 = 'e' (adjacent pair)

      • char1_ascii = 104, char2_ascii = 101 (ASCII values)

      • pair_score = abs(104 - 101) = 3

      • total_score = 3 (updated)

    • Iteration 2:

      • index = 1 (second character 'e')

      • char1 = 'e', char2 = 'l' (adjacent pair)

      • char1_ascii = 101, char2_ascii = 108 (ASCII values)

      • pair_score = abs(101 - 108) = 7

      • total_score = 10 (updated)

    • Iteration 3:

      • index = 2 (third character 'l')

      • char1 = 'l', char2 = 'l' (adjacent pair)

      • char1_ascii = 108, char2_ascii = 108 (ASCII values)

      • pair_score = abs(108 - 108) = 0

      • total_score = 10 (no change)

    • Iteration 4:

      • index = 3 (fourth character 'l')

      • char1 = 'l', char2 = 'o' (adjacent pair)

      • char1_ascii = 108, char2_ascii = 111 (ASCII values)

      • pair_score = abs(108 - 111) = 3

      • total_score = 13 (updated)

  3. Iteration Summary (Character Pair Scores):

    • The table below summarizes the calculations performed during each iteration of the loop.

    Iteration

    Char 1

    Char 2

    ASCII 1

    ASCII 2

    Pair Score

    Total Score

    1

    h

    e

    104

    101

    3

    3

    2

    e

    l

    101

    108

    7

    10

    3

    l

    l

    108

    108

    0

    10

    4

    l

    o

    108

    111

    3

    13

  4. Function Returning:

    • The function returns the final calculated total_score, which is 13.

June 2 -> 344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

  • Input: s = ["h","e","l","l","o"]

  • Output: ["o","l","l","e","h"]

Example 2:

  • Input: s = ["H","a","n","n","a","h"]

  • Output: ["h","a","n","n","a","H"]

Constraints:

  • 1 <= s.length <= 10^5

  • s[i] is a printable ascii character.

Approach 1: Two Pointer Technique

def reverseString1(s: List[str]) -> None: """ This function reverses the order of elements in a character array in-place. This function uses a two-pointer approach, where one pointer starts from the beginning (`left_index`), and the other one starts from the end of the array (`right_index`). The characters at these two pointers are swapped, and the pointers are moved towards each other. This carries on until the two pointers meet or pass each other, which suggests that the array is now reversed. The time complexity of this function is O(n), where `n` is the number of elements in the list. The space complexity is O(1) because it operates directly on the input list and uses a constant amount of additional memory for the index variables. """ left_index = 0 right_index = len(s) - 1 while left_index < right_index: # Swap the characters at the current left and right indices s[left_index], s[right_index] = s[right_index], s[left_index] left_index += 1 right_index -= 1

Understanding the Core Idea

The central concept of this solution is to leverage the two-pointer technique to reverse the string in-place. This approach efficiently swaps characters from both ends of the string, moving towards the center.

  • In-Place Reversal: The solution modifies the input array directly, adhering to the extra memory constraint.

  • Two-Pointer Mechanism: By using two pointers that start at opposite ends and move towards each other, we ensure that each character is swapped exactly once.

  • Midpoint Convergence: The process naturally stops when the pointers meet or cross, indicating that all necessary swaps have been completed.

Code Walkthrough

  1. Initialization:

    left_index = 0 right_index = len(s) - 1

    We set up two pointers: left_index at the start of the string and right_index at the end. These will be used to traverse the string from both ends simultaneously.

  2. Iteration and Swapping:

    while left_index < right_index: s[left_index], s[right_index] = s[right_index], s[left_index] left_index += 1 right_index -= 1

    This loop continues as long as left_index is less than right_index, ensuring we stop in the middle of the string. In each iteration:

    • We swap the characters at left_index and right_index using Python's multiple assignment feature.

    • We then move left_index one step to the right and right_index one step to the left.

    This process effectively reverses the string by swapping characters from the outside in.

  3. Implicit Return: The function doesn't explicitly return anything (-> None), as it modifies the input list in-place. The reversed string is available in the original s list after the function execution.

Complexity Analysis

Time Complexity:

  • , where is the length of the input string. This is because we iterate through half of the string, performing constant-time operations (swapping) for each pair of characters. Even though we only traverse half the string in Big notation, this is still considered .

Space Complexity:

  • , as we use only a constant amount of extra space (the two index variables) regardless of the input size. The reversal is performed in-place, modifying the original input array without requiring any additional data structures that scale with input size.

Example

Input:

s = ["h","e","l","l","o"]

Step-by-Step Walkthrough

  1. Initialization:

    • left_index is set to 0, pointing to the first element ('h').

    • right_index is set to 4 (len(s) - 1), pointing to the last element ('o').

  2. Main Loop (Reversing In-Place):

    • Iteration 1:

      • Before swap: s = ['h', 'e', 'l', 'l', 'o'], left_index = 0, right_index = 4

      • Swap: The characters at index 0 ('h') and index 4 ('o') are swapped.

      • After swap: s = ['o', 'e', 'l', 'l', 'h'], left_index = 0, right_index = 4

      • Update pointers: left_index is incremented to 1, and right_index is decremented to 3.

    • Iteration 2:

      • Before swap: s = ['o', 'e', 'l', 'l', 'h'], left_index = 1, right_index = 3

      • Swap: The characters at index 1 ('e') and index 3 ('l') are swapped.

      • After swap: s = ['o', 'l', 'l', 'e', 'h'], left_index = 1, right_index = 3

      • Update pointers: left_index is incremented to 2, and right_index is decremented to 2.

  3. Iteration Summary (Swaps and List States)

    Iteration

    Left Index

    Right Index

    List (s)

    1

    0

    4

    ['o', 'e', 'l', 'l', 'h']

    2

    1

    3

    ['o', 'l', 'l', 'e', 'h']

  4. Loop Termination:

    • When left_index and right_index cross (at index 2), the array reversal is complete.

    • The final reversed array is s = ['o', 'l', 'l', 'e', 'h'].

    • The function has successfully reversed the input array in-place. It does not return a new array but modifies the input array directly.

Last modified: 02 July 2024
June 2024 Daily ExercisesJune 2024, Week 2: June 3rd - June 9th