This is the main discussion thread generated for Reverse A String.

I encountered an issue running Java code on the platform that may need checking to allow learners just focus on the tasks at hand

Error: Main method not found in class Main, please define the main method as:
public static void main(String[] args)
or a JavaFX application class must extend javafx.application.Application

Hey Stanslaus Odhiambo,

It's a common confusion with Java that we're working on solving. For now, there are two differences:

1) To execute "Run Tests", the main method needs to be commented out. This is because we wrap the user's input with our own class and run our own main method.
2) With "Run Code", the main method must be kept, because the execution environment is different.

I'm working with the team to solve for this, as it's not a great UX -- but hopefully that clears it up.

Thanks Jake for the clarification

In an interview setting does the one line solution "return str[::-1]" suffice in python syntax or is the best code solution to showcase using the two pointer technique?

I also have another question on the solution provided for this problem using the Two-Pointer Method. I dont really understand what the two lines are for using temp:
temp = StrList[Pointer1]
strList[Pointer2] = temp

I am unclear of what these two lines actually do. I understand the purpose of the two pointers where they are basically just flip-flopping locations in the array, but im not 100% sure what the two lines using temp really does?

Hi Tim,

Great questions!

I typically advise folks interviewing to actually mention that there's a built in method. Interviewers will almost surely never allow it as the final answer, but it demonstrates mastery of the language - e.g. "I'm going to implement this from scratch, but wanted to call out that we can just call the [::-1] or reverse() method, which would be the way to do it in production."

The two lines outlined are just doing a swap. Using the two pointer method doesn't necessitate swapping, sometimes you just have two pointers that track two different things (no flip-flopping locations happens, it's literally two variables/references). However, in this case specifically, we do an in-place swap in order to achieve a new string value.

something that stuck out for me: since string is immutable, it is not possible to achieve better than O(n) space complexity

Hi,

Since appending to a string is O(N), wouldn't appending to a string with the two pointer approach of swapping still be quadratic time?

Hi supuilam,

In Java, C#, JavaScript, Python and Go, strings are immutable, so that is correct. In Ruby, PHP, and C, strings are mutable. So it depends on the language.

Hi fanfanfan,

That nuance is correct. Appending to a string can be O(1) or O(n) depending on the implementation-- related to the above comment. Instead of appending directly to a mutable string, you can also keep an ArrayList/dynamic array that you append to-- in that case, worst time complexity is O(n) but amortized, average complexity is O(1).

It's good to mention this during implementation!

Why not use Java's toCharArray and then swap the indices using a temp char? I know this takes O(n) space in the background, but doesn't the recursive solution actually take 0(n) stack space?

In order to implement the two-pointer approach you need to call len(). Since len() has to pass through the whole string, doesn't that just negate the benefit of using two pointers? Essentially you're doing one and a half passes through the string?

This was my solution, which requires just 1 pass through the string because it doesn't call len():

def reverseString(s):
    new_string = ""
    for char in s:
        new_string = char + new_string

    return new_string

Thoughts?

Ignore my comment regarding the len() function. I thought it is O(n) but upon further reading I found out that it is actually O(1), so my statement is invalid. It's O(1) because the length is a fundamental property of iterables like lists, so calling len() essentially just looks up the object's __len__ method and returns it (i.e. time is independent of iterable length).

The provided solution, shown below, fails to meet the Constant Space Complexity constraint (O(1)). In fact, I would argue that this constraint is not achievable in tandem with the Linear Time Complexity constraint (O(n)). In languages with immutable strings, you either trade memory for speed, or vise versa, but you can't get both.

This solution uses the .split() method to build an array of proportional size to the input string, thus using O(n) Space Complexity. There are many similar approaches such as using a String Builder which leverages a buffer array, but this too requires an array of proportional size.

Alternatively, you use simply loop through each character and perform a swap operation on the original string. However, due to the immutability of the string, you would be creating a new string each time. And since you'll need to perform a swap at least n/2 times, rebuilding the string each time, this would result in Quadratic Time Complexity (O(n^2)).

My point is, the question is flawed -- the ideal constraints are not achievable.

function reverseString(str) {
  let strArr = str.split('');
  let start = 0;
  let end = str.length - 1;

  while (start <= end) {
    const temp = strArr[start];
    strArr[start] = strArr[end];
    strArr[end] = temp;
    start++;
    end--;
  }

  return strArr.join('');
}