Codility ‘Str Symmetry Point’ Solution

Short Problem Definition:

Find a symmetry point of a string, if any.

Link

StrSymmetryPoint

Complexity:

expected worst-case time complexity is O(length(S));

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Execution:

This problem gave me a lot of headache. It is so trivial I that over-complicated it. I thought that you should find a symmetry point at any possible position, ignoring the residual characters. You would obviously try to maximize the length of this symmetrical sub-array. I was not able to come with any O(S) algorithm for this problem derivation. So just to remind you, this problem is a simple palindrome check. Additionally, you drop all evenly sized strings as their symmetry point is between the indexes.

Solution:
def solution(S):
    l = len(S)

    if l % 2 == 0:
        return -1

    mid_point = l // 2

    for idx in xrange(0, mid_point):
        if S[idx] != S[l - idx - 1]:
            return -1

    return mid_point

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Nicolas

    Hi Martin, thanks for share these solutions, here is mine for this one:

    def solution(S):
    ””””’n = len(S)
    ””””’if n>2:
    ”””””””””halfidx = n/2
    ”””””””””if S[:halfidx] == S[halfidx+1:][::-1]:
    ”””””””””””””’return halfidx
    ”””””””””else:
    ”””””””””””””’return -1
    ””””’else:
    ”””””””””if n== 0:
    ”””””””””””””’return -1
    ”””””””””else:
    ”””””””””””””’return 0

    • Hi Nicolas,

      I am glad they help. Should you find any mistake or should the solution no longer be valid, please do let me know 🙂