# Palindrome

**URL:** <https://discourse.julialang.org/t/palindrome/124054>\
**Category:** New to Julia\
**Tags:** strings\
**Created:** [December 21, 2024, 7:55am UTC](https://discourse.julialang.org/t/palindrome/124054 "2024-12-21T07:55:44Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [December 21, 2024, 7:55am UTC](https://discourse.julialang.org/t/palindrome/124054/1 "2024-12-21T07:55:44Z")

</div>

Hello,  
I want to write a program that determines whether a sentence is a palindrome or not. I wrote the following program and it works, but I want to know if this piece of code is flawed from a programming science perspective:

```julia
function palindrome(str)
    ch = ""
    temp = ""
    str = lowercase(str)
    for i = 1 : length(str)
        if isletter(str[i])
            ch *= str[i]
        end
    end
    for i = length(ch) : -1 : 1
        temp *= ch[i]
    end
    if ch == temp
        return true
    else
        return false
    end
end

function main()
    print("Please enter a string: ")
    str = readline()
    if palindrome(str)
        println(str," is a palindrome.")
    else
        println(str," is not a palindrome.")
    end
end

main()

```

Thank you.

---

<div class="post-metadata">

**Author:** ![g-gundam](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/g-gundam/32/47593_2.png) [@g-gundam](https://discourse.julialang.org/u/g-gundam)\
**Post date:** [December 21, 2024, 8:40am UTC](https://discourse.julialang.org/t/palindrome/124054/2 "2024-12-21T08:40:08Z")

</div>

You seem to like to do character-by-character parsing, but you don’t have to do those kinds of things as much anymore.

```julia
palindrome2(s) = s == reverse(lowercase(s))

```

It’s not exactly the same, because I didn’t do the `isletter` part, but it could be added without too much more effort.

```julia
palindrome3(s) = lowercase(filter(isletter, s)) == reverse(lowercase(filter(isletter, s)))

```

You’re treating Julia like it’s C, but it’s got a lot more to offer.

UPDATE: I added a missing lowercase call to palindrome3.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [December 21, 2024, 9:46am UTC](https://discourse.julialang.org/t/palindrome/124054/3 "2024-12-21T09:46:43Z")

</div>

> [@hack3rcon](#):
>
> ```julia
> for i = length(ch) : -1 : 1
> temp *= ch[i]
> end
> 
> ```

Incrementally building a string in this way is not recommended. A pre-allocated character array will perform better. But unless there’s a good reason not to, just use @g-gundam’s one-liner solutions.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [December 21, 2024, 10:40am UTC](https://discourse.julialang.org/t/palindrome/124054/4 "2024-12-21T10:40:29Z")

</div>

Well, the original specification is slightly different in that `lowercase` is applied to both sides as well. A short translation would be

```julia
palindrome(str) = let ch = filter(isletter, lowercase.(str))
                      reverse(ch) == ch
                  end

```

Imho, this should be two functions as deciding what to consider and checking for a palindrome are two orthogonal concerns, i.e.,

```julia
normalize(str) = filter(isletter, lowercase.(str))
ispalindrome(seq) = reverse(seq) == seq

const mypalindrome = ispalindrome 

```

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 21, 2024, 11:04am UTC](https://discourse.julialang.org/t/palindrome/124054/5 "2024-12-21T11:04:00Z")

</div>

> [@greatpet](#):
>
> A pre-allocated character array will perform better.

Or don’t create a new `String` at all, and instead just compare (valid) characters in the input `str` by moving from front to back and back to front simultaneously 🙂

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 21, 2024, 11:25am UTC](https://discourse.julialang.org/t/palindrome/124054/6 "2024-12-21T11:25:28Z")

</div>

> [@hack3rcon](#):
>
> I want to know if this piece of code is flawed from a programming science perspective

This depends on what your goals are. It is neither the most efficient implementation (as you create multiple extra `String`s (in a suboptimal way, cf. @greatpet 's reply)), nor the shortest implementation (cf. @g-gundam, and even if you like to iterate explicitly, you could also just use `return ch == temp`, for example). I would also argue that “a12a” is not a palindrome.

But most often you don’t really need the fastest or shortest implementation. In this example, the IO time will likely dwarf the execution time for `palindrome`. In any case, the user will not notice the difference between 1 ns and 1 ms.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [December 21, 2024, 12:22pm UTC](https://discourse.julialang.org/t/palindrome/124054/7 "2024-12-21T12:22:07Z")

</div>

Hello,  
Thank you so much for your reply.  
I’m a newbie and learning Julia. I haven’t learned arrays yet. I have currently learned numbers, for and while loops, functions, and characters and strings in Julia.  
With my current knowledge, is this program well written?

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 21, 2024, 12:59pm UTC](https://discourse.julialang.org/t/palindrome/124054/8 "2024-12-21T12:59:44Z")

</div>

Is there a specific reason why you think your code might be “flawed”? It seems fine enough to me.

> [@eldee](#):
>
> just compare (valid) characters in the input `str` by moving from front to back and back to front simultaneously

If you don’t want to use functions like (`Iterators.`)`filter` or `reverse`, I’m personally a bit more partial to something like

```julia
function is_palindrome(str)
    i = 1 # moves front to back
    j = length(str) # moves back to front

    while i <= length(str) && j >= 1 
        # Move i forward to the first valid next character
        if !isletter(str[i])
            i += 1
            continue
        end

        # Move j backward to the first valid previous character
        if !isletter(str[j])
            j -= 1
            continue
        end

        lowercase(str[i]) == lowercase(str[j]) || return false
        i += 1
        j -= 1
    end
    return true
end

```

the interpretation of which might also be a good exercise in control flow (you could make it a bit easier by using nested `while` loops, potentially moved to a different function). I would also just leave out the `isletter` checks and `lowercase` conversion, but that depends on your definition of palindrome.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [December 21, 2024, 1:18pm UTC](https://discourse.julialang.org/t/palindrome/124054/9 "2024-12-21T13:18:26Z")

</div>

String indexing has quadratic time complexity due to the UTF-8 encoding. Using the built-in `filter` and `reverse` will be faster.

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 21, 2024, 3:31pm UTC](https://discourse.julialang.org/t/palindrome/124054/10 "2024-12-21T15:31:58Z")

</div>

String indexing seems pretty constant time to me?

> **Relevant code in string.jl**
>
> ```julia
> @assume_effects :foldable @inline function codeunit(s::String, i::Int)
> @boundscheck checkbounds(s, i)
> b = GC.@preserve s unsafe_load(pointer(s, i))
> return b
> end
> 
> @propagate_inbounds function getindex(s::String, i::Int)
> b = codeunit(s, i)
> u = UInt32(b) << 24
> between(b, 0x80, 0xf7) || return reinterpret(Char, u)
> return getindex_continued(s, i, u)
> end
> 
> function getindex_continued(s::String, i::Int, u::UInt32)
> if u < 0xc0000000
> # called from `getindex` which checks bounds
> @inbounds isvalid(s, i) && @goto ret
> string_index_err(s, i)
> end
> n = ncodeunits(s)
> 
> (i += 1) > n && @goto ret
> @inbounds b = codeunit(s, i) # cont byte 1
> b & 0xc0 == 0x80 || @goto ret
> u |= UInt32(b) << 16
> 
> ((i += 1) > n) | (u < 0xe0000000) && @goto ret
> @inbounds b = codeunit(s, i) # cont byte 2
> b & 0xc0 == 0x80 || @goto ret
> u |= UInt32(b) << 8
> 
> ((i += 1) > n) | (u < 0xf0000000) && @goto ret
> @inbounds b = codeunit(s, i) # cont byte 3
> b & 0xc0 == 0x80 || @goto ret
> u |= UInt32(b)
> @label ret
> return reinterpret(Char, u)
> end
> 
> ```
> 
> In particular, for ASCII characters `getindex_continued` will never be called.

Also note that

```julia-repl
julia> s = "abγd"
"abγd"

julia> s[2]
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)

julia> s[3]
'γ': Unicode U+03B3 (category Ll: Letter, lowercase)

julia> s[4]
ERROR: StringIndexError: invalid index [4], valid nearby indices [3]=>'γ', [5]=>'d'
Stacktrace:
 [1] string_index_err(s::String, i::Int64)
   @ Base .\strings\string.jl:12
 [2] getindex_continued(s::String, i::Int64, u::UInt32)
   @ Base .\strings\string.jl:472
 [3] getindex(s::String, i::Int64)
   @ Base .\strings\string.jl:464
 [4] top-level scope
   @ REPL[12]:1

julia> s[5]
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)

```

For non-ASCII strings the above `is_palindrome` and original `palindrome` implementations would then fail (and are hence indeed flawed to some extent), while `reverse` would work. As a compromise you could change the indices `i` and `j` into `Char`s obtained from iterating over `str` and `Iterators.reverse(str)` via `iterate`.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [December 21, 2024, 4:57pm UTC](https://discourse.julialang.org/t/palindrome/124054/11 "2024-12-21T16:57:47Z")

</div>

You’re conpletely right, I totally forgot that Julia guaranteed constant time string indexing. It’s just that the `getindex` result may not be an actual character.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [December 21, 2024, 4:58pm UTC](https://discourse.julialang.org/t/palindrome/124054/12 "2024-12-21T16:58:28Z")

</div>

> [@greatpet](#):
>
> You’re conpletely right, I totally forgot that Julia guaranteed constant time string indexing. It’s just that the `getindex` result may not be an actual character.

You just need to use `nextind` and `prevind` to increment and decrement the index, rather than `+= 1` and `-= 1`.

---

<div class="post-metadata">

**Author:** ![g-gundam](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/g-gundam/32/47593_2.png) [@g-gundam](https://discourse.julialang.org/u/g-gundam)\
**Post date:** [December 21, 2024, 5:00pm UTC](https://discourse.julialang.org/t/palindrome/124054/13 "2024-12-21T17:00:58Z")

</div>

Thanks for cleaning it up.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [December 22, 2024, 6:44am UTC](https://discourse.julialang.org/t/palindrome/124054/14 "2024-12-22T06:44:48Z")

</div>

Hello,  
Thanks again.  
That’s why I asked because I’m a novice and I want to know if I’m on the right track or not?  
How can I calculate the execution time of the program?

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 22, 2024, 11:32am UTC](https://discourse.julialang.org/t/palindrome/124054/15 "2024-12-22T11:32:39Z")

</div>

I’d say you’re on the right track if you don’t want to use too many of the built-in features of the language. But as highlighted by @greatpet and @stevengj, Unicode strings (using characters from outside the Latin alphabet, requiring potentially more than 1 byte for a given `Char`) will lead to complications and we cannot just use simple incremental indexing (`for i = 1:length(str)` or `i += 1`), though `for i = eachindex(str)` is fine. As long as you intend the user to only supply simple ASCII strings (which is mostly sufficient for the English language), you don’t have to worry too much about that though, but it’s still good to keep in mind (and document).

> [@hack3rcon](#):
>
> How can I calculate the execution time of the program?

You could look into theoretical computational complexity (the constant time and quadratic time complexity mentioned above). But you could also just measure the execution time, e.g. via BenchmarkTools.jl’s `@btime` and `@benchmark`:

```julia
using BenchmarkTools
using Random # for randstring to generate a random String

function palindrome1(str) # Made Unicode-proof
    ch = ""
    temp = ""
    str = lowercase(str)

    i = 1 # Will be a byte-level index
    while i <= sizeof(str) # sizeof returns the byte-length
        if isletter(str[i])
            ch *= str[i]
        end
        i = nextind(str, i)
    end
    
    i = sizeof(ch) + 1 # Beyond the last byte (which might or might not already correspond to a full Char)
    i = prevind(ch, i) # Now the start of the last Char in ch
    while i >= 1
        temp *= ch[i]
        i = prevind(ch, i)
    end

    return ch == temp
end

palindrome2(str) = let ch = filter(isletter, lowercase.(str)) # (Already worked fine)
    reverse(ch) == ch
end

function palindrome3(str) # Also made Unicode-proof
    i = 1 # moves front to back
    j = sizeof(str) + 1; j = prevind(str, j) # moves back to front

    while i <= j # (Note: Changed to exploit symmetry)
        # Move i forward to the first valid next character
        if !isletter(str[i])
            i = nextind(str, i)
            continue
        end

        # Move j backward to the first valid previous character
        if !isletter(str[j])
            j = prevind(str, j)
            continue
        end

        lowercase(str[i]) == lowercase(str[j]) || return false
        i = nextind(str, i)
        j = prevind(str, j)
    end
    return true
end

# Below we return the minimal (best) execution time over a number of runs (determined automatically)
# for checking that a random string (not the same one each time) of length 1000 is a palindrome.
# We do not include the creation of the string to test in the timing.
# (By default randstring only uses standard Latin letters and digits, hence only ASCII character)

# Very likely non-palindromes:
@btime palindrome1(s) setup=(s = randstr(1000)); # 97.800 μs (1590 allocations: 673.77 KiB)
@btime palindrome2(s) setup=(s = randstr(1000)); # 11.800 μs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(1000)); # 19.358 ns (0 allocations: 0 bytes)
# (We immediately return False after comparing the first and last character.)

# Palindromes:
@btime palindrome1(s) setup=(s = randstr(500); s *= reverse(s)); # 96.200 μs (1556 allocations: 646.67 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s)); # 11.700 μs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s)); # 10.900 μs (0 allocations: 0 bytes)

```

For interactive usage 100 µs is negligible, so we really don’t have to worry much about computational efficiency here.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [December 22, 2024, 3:14pm UTC](https://discourse.julialang.org/t/palindrome/124054/16 "2024-12-22T15:14:44Z")

</div>

> [@eldee](#):
>
> `j = sizeof(str) + 1; j = prevind(str, j)`

Is this different from simply using `j = lastindex(str)`?

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 22, 2024, 3:32pm UTC](https://discourse.julialang.org/t/palindrome/124054/17 "2024-12-22T15:32:39Z")

</div>

No, that should be the same. For some reason (I guess confusion between byte- and `Char`-indexing) I just didn’t think of `lastindex`, which would be better in every way.

```julia-repl
help?> prevind
search: prevind

  prevind(str::AbstractString, i::Integer, n::Integer=1) -> Int

    • Case n == 1
       (...) If i is equal to ncodeunits(str)+1 return lastindex(str). Otherwise throw BoundsError.
(...)

```

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [December 24, 2024, 6:27am UTC](https://discourse.julialang.org/t/palindrome/124054/18 "2024-12-24T06:27:10Z")

</div>

Hello,  
Thanks again.  
Do I just need to insert the following two lines at the beginning of my code and the calculation will be performed automatically?

```julia
using BenchmarkTools
using Random

```

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [December 24, 2024, 9:32am UTC](https://discourse.julialang.org/t/palindrome/124054/19 "2024-12-24T09:32:45Z")

</div>

No, to time a piece of code you indeed first need to import BenchmarkTools.jl, but then also prepend `@benchmark` or `@btime` (etc.) to the code block.

```julia-repl
julia> using BenchmarkTools

julia> @benchmark rand(1000)
BenchmarkTools.Trial: 10000 samples with 10 evaluations.
 Range (min … max): 810.000 ns … 4.377 ms ┊ GC (min … max): 0.00% … 99.93%
 Time (median): 1.940 μs ┊ GC (median): 0.00%
 Time (mean ± σ): 4.199 μs ± 46.922 μs ┊ GC (mean ± σ): 22.93% ± 3.28%

  ▃ ▅█▅▄▃▃▃▃▂▁ ▂▄▅▄▄▃▃▂▂▁▁ ▂
  █▇▆▆▆▆▅████████████▆▆▅▅▃▄▁▁▁▁▃▃▄▃▁▅▆▇███████████████▇████▇▇▇ █
  810 ns Histogram: log(frequency) by time 8.24 μs <

 Memory estimate: 7.94 KiB, allocs estimate: 1.

julia> @btime begin
           x = rand(100)
           y = rand(100)
           x .+ y
       end;
  361.611 ns (3 allocations: 2.62 KiB)

```

There are some caveats regarding global variables, which you should interpolate using `$`:

```julia-repl
julia> x = rand(1000);

julia> @btime x .^ 2;
  1.590 μs (8 allocations: 8.16 KiB)

julia> @btime $x .^ 2;
  467.172 ns (1 allocation: 7.94 KiB)

```

Note here that we really only require one allocation, to store the output `Vector{Float64}` of length 1000 containing the squared values.

In general, take a look at [the online documentation](https://juliaci.github.io/BenchmarkTools.jl/stable/), or use the help mode of the REPL (by entering ‘?’ as the first input character)

```julia-repl
help?> @benchmark
  @benchmark <expr to benchmark> [setup=<setup expr>]

  Run benchmark on a given expression.

  Example
  ≡≡≡≡≡≡≡
(...)

```

---

<div class="post-metadata">

**Author:** ![technocrat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/technocrat/32/220947_2.png) [@technocrat](https://discourse.julialang.org/u/technocrat)\
**Post date:** [December 27, 2024, 6:20am UTC](https://discourse.julialang.org/t/palindrome/124054/20 "2024-12-27T06:20:14Z")

</div>

What I found in learning Julia this year is that the same style of imperative/procedural coding in C carries over easily, and “duck typing” like Python is well tolerated.

But I also learned two important aspects of Julia that reveal its power.

The first is the option to strongly type arguments to functions, including the ability to define specific types to implement data structures that can allow complex data to be packaged in a way that minimizes the manual operations need to be done to analyze your data.

The second is arrays, indexing over them and “broadcasting” with the `.` operator, which applies a function to each element. What can be naively done with a multiplicity of intermediate objects can be wrapped in a function and handled as a unit.

Keep an eye out for those as you continue learning.