[Two Pointers] Valid Palindrome

Valid Palindrome Problem

Statement

Write a function that takes a string, s, as an input and determines whether or not it is a palindrome.

 

Constraints

• 1≤1≤ s.length ≤2×10^5≤2×10^5
• The string s will not contain any white space and will only consist of ASCII characters(digits and letters).

문자열 s의 길이가 최소 1에서 최대 200000까지 가능.

문자열의 길이는 최소 1 이상이므로, 빈 문자열은 들어올 수 없음

200,000까지 가능하므로, 시간 복잡도가 너무 크면 성능이 떨어질 수 있음

O(n): 선형 탐색 

O(nlogn): 정렬 -> 가능하지만 조심해야 함

O(n²) : 최악의 경우 40,000,000,000번 연산

 

Approaches

1. Naive approach: Reversing the string and then compare the reversed string with the original string. If they match, the original string is a valid palindrome. Although this solution has a linear time complexity, it requires extra space to store the reversed string, making it less efficient in terms of space complexity. Therefore, we can use an optimized approach to save extra space.

2. Optimized approach using two pointers: The efficient use of two pointers converging from opposite ends toward the middle of the string. One pointer gegins from the start and moves forward, while the other starts from the end and moves backward in the string. As they converge toward each other, they compare characters at each step to identify any mismatch. The string is a palindrome if these pointers converge in the middle without discovering mismatching characters. This approach would allow us to solve this problem in linear time without any additional space complexity or the use of built-in functions. This is because we will traverse the array from the start and the end simultaneously to reach the middle of the string.

 

Solution

- Initalize two pointers and move them from opposite ends.

- The first pointer starts at the beginning of the string and moves toward the middle, while the second pointer starts at the end and moves toward the middle.

- Compare the elements at each position to detect a nonmatching pair.

- If both pointers reach the middle of the string without encountering a nonmatching pair, the string is a palindrome.

 

1. Initialize two pointers at the beginning and end of the string

2. Check whether or not the current pair of characters is identical

3. If they are not identical, return FALSE. Otherwise, move both pointers by one index toward the middle.

4. Keep traversing them toward the middle until they meet

5. It we reach the middle of the string without finding a mismatch, return TRUE.

 

def is_palindrome(s):
    s = s.lower() # 새로운 문자열 생성으로 공간 복잡도 -> O(n) 
    left = 0
    right = len(s) - 1
    
    while left <= right:
    	if s[left] != s[right]:  # Check if characters at both ends match
      		return False
    	left += 1
    	right -= 1  # Move both pointers inward
    return True  # If all characters matched, it's a palindrome

def is_palindrome(s):
    left = 0
    right = len(s) - 1
    
    while left <= right:
    	if s[left].lower() != s[right].lower():  # Check if characters at both ends match
      		return False
    	left += 1
    	right -= 1  # Move both pointers inward
    return True  # If all characters matched, it's a palindrome

def is_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left = left + 1 
        right = right - 1
    return True

 

 

Time complexity

The time complexity is O(n), where n is the number of characters in the string. However, our algrithm will only run (n/2) times, since two pointers are traversering toward each other.

 

Space complexity

The space complexity is O(1), since we use constant space to store two indexes.

투 포인터를 사용하면 추가적인 배열이나 리스트를 만들지 않기 때문에 공간 복잡도는 O(1) 

포인터 (변수) 선언이 공간을 차지하긴 하지만, 추가적인 데이터 구조(배열, 리스트, 딕셔너리 등)를 만들지 않는다면 공간 복잡도는 O(1)로 간주. 상수 개수(고정된 개수)만 사용하기 때문에 공간 복잡도  O(1)를 유지