🗓️Day 07 – String
Topics: String
Problem solved:
#344 - Reverse String
#541 - Reverse String II

---

🧩Problem solution – 344. Reverse String

link

💡Problem description

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 <= 105
s[i] is a printable ascii character.

🧭Thought Process

Just use two pointers.

💻Code Implementation

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int i = 0,j = n-1;
        while(i<j){
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(1)

🧩Problem solution – 541. Reverse String II

link

💡Problem description

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:
Input: s = “abcdefg”, k = 2
Output: “bacdfeg”

Example 2:
Input: s = “abcd”, k = 2
Output: “bacd”

Constraints:

1 <= s.length <= 10 ⁴
s consists of only lowercase English letters.
1 <= k <= 10 ⁴

🧭Thought Process

It’s a liitle similar like the last one. The only thing that need to pay attention is where to start and where to end.

💻Code Implementation

class Solution {
public:
    string reverseStr(string s, int k) {
        int start = 0, end = k - 1;
        int n = s.size();
        while(end<n){
            int i = start, j = end;
            char temp;
            while(i<j){
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
                i++;
                j--;
            }
            start = start + 2*k;
            end = end + 2*k;
        }
        if(start<n){
            char temp;
            n--;
            while(start<n){
                temp = s[start];
                s[start] = s[n];
                s[n] = temp;
                start++;
                n--;
            }
        }

        return s;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(1)