Solution by kevin.white.bcn


  • 0
    K

    Approach #1 O(n/k) complexity

    Intuition

    Only examine the first k characters of each 2k group of characters.

    Algorithm

    s = "abcdefg"
    k = 2

    Our objective is to output "bacdfeg". We immediatly observe that characters "cdg" do not change. This leads to the intuition that we need only examine the first k characters of each 2k group:

    // s = "abcdefg", s.Length = 7, k = 2
    for(int n = 0; n < s.Length; n+=2*k) {
      // values of n are [0,4] = 2 iterations
    }
    

    Now we have a method of iterating each 2k group, we now need to reverse the first k characters of each group. Gotcha: do not iterate beyond the length of s. So, we need to now iterate from n to n + k or s.Length, whichever is smaller!

    int m = Math.Min(n + k, s.Length);
    
    for(int j = n; j < m; j++) {
      // Remaining algorithm
    }
    
    

    The outer-loop iterates each 2k group, the inner-loop the first k characters of each 2k group. Now we simply reverse the characters.

    // Calculate relative position in group e.g. first-char has pos 0, second-char pos 1, ...
    int pos = j - n;
    
    // Calculate the new position to reverse the string (i.e. place characters beginning from the end)
    int newPos = m - pos - 1;
    
    // Simply set the character in the output string
    a[newPos] = s[j];
    

    A table helps visualise the logic:

    n m = (Math.min(n+k, s.Length)) j pos = (j - n) newPos = (m - pos - 1)
    0 2 0 0 1
    0 2 1 1 0
    4 6 4 0 5
    4 6 5 1 4

    We can see from the above table that the character at j is being moved to the correct new position (newPos). Producing a table like the above with a few different inputs was key to solving the problem.

    C#

    public class Solution {
      // Catch error conditions
      if (string.IsNullOrEmpty(s) || k < 2) return s;
      
      char[] a = s.ToCharArray();
    
      // Outer-loop moves nt ot he beginning of each 2k group
      for(int n = 0; n < s.Length; n += 2*k)
      {
        // Determine where the current reverse should end: either (a) after transversing k characters or (b) coming to the end of the string (whichever is smaller)
        int m = Math.Min(n + k, s.Length);
                   
        // Inner-loop performs the actual reversing of the characters
        for(int j = n; j < m; j++)
        {
          // Calculate position of character within group e.g. first character is pos 0, second pos 1 ...
          int pos = j - n;
    
          // Calculate the position of the new character, which is simply at the end of the group - pos
          int newPos = m - pos - 1;
    
          // Place the character in the new position
          a[newPos] = s[j];
        }
      }
    
      return new string(a);
    }
    

    Complexity Analysis

    • Time complexity : $$O(n/k)$$
      NOTE: this is an approximation but a good fit.
    • Space complexity : $$O(1)$$

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.