# LeetCode 344: Reverse String (LaTeX)

Write a function that reverses a string. The input string is given as an array of characters char[].

## Example

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]


Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]


## Notes

• The original question requires in-place modification with $O(1)$ memory. Since LaTeX does not have proper support for ordered lists, this requirement is discarded.

## Solution

\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{expl3}

\begin{document}
\ExplSyntaxOn

\cs_set:Npn \reverse_string:n #1 {
% convert token list to string
\str_set:Nn \l_tmpa_str {#1}
% use a sequence to save the string
\seq_gclear:N \g_tmpa_seq
% store each character in \l_tmpa_str in \l_tmpa_seq
% use \exp_args:NV to expand the first argument
\exp_args:NV \str_map_variable:nNn { \l_tmpa_str } { \l_tmpb_str }
{ \seq_gput_right:NV \g_tmpa_seq \l_tmpb_str }
% pop each element in \l_tmpa_str from right side
\bool_do_while:nn {
% reverse the value of \seq_if_empty_p:N
\bool_if:nTF {\seq_if_empty_p:N \g_tmpa_seq} {\c_false_bool} {\c_true_bool}
}
{
\seq_gpop_right:NN \g_tmpa_seq \l_tmpa_tl
% generate output
\tl_use:N \l_tmpa_tl
}
}

\newcommand{\reversestring}[1]{\reverse_string:n {#1}}

\ExplSyntaxOff

\reversestring{abcde12345}

\end{document}


### Output

54321edcba

• There really isn’t much choice when it comes to reversing a string in LaTeX, because LaTeX does not provide a way to read something “from behind”. In this solution, I decide to construct a stack with l3seq to reverse the order of characters. Another way of doing so may be using an integer loop with \str_item:nn. But this macro seems to work by discarding characters before the desired index, so the performance may be bad.
• The performance of this code isn’t great either. I tried to reverse 10,000 characters, and it takes around 10 seconds to finish. I think it is because the implementation of l3seq isn’t very efficient either.
• I guess the lesson learned is that don’t reverse long strings in LaTeX. Do it somewhere else!

## Tips for LaTeX programming

• Due to the expansion mechanism of LaTeX, it is very inconvenient for a macro to return value(s).
• Therefore, if the intended return value is to be put into text, simply use the result so that it is inserted into the output stream.
• If the intended return value is to be used by another macro, store this value into a global variable and use the value.

LaTeX3 has already provided a command to reverse tokens (\tl_reverse:n), which allows us to write a simpler program like so. However, after some experiments, I find out that this is no faster than my own version. This may imply that the internal implementation of this function is similar.

\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{expl3}

\begin{document}
\ExplSyntaxOn

\cs_set:Npn \reverse_string:n #1 {
\tl_reverse:n {#1}
}

\newcommand{\reversestring}[1]{\reverse_string:n {#1}}

\ExplSyntaxOff

\reversestring{abcde12345}

\end{document}


It is possible to use l3intarray package to facilitate string reversal. The following code is capable of reversing 10,000 characters in no time. However, the drawbacks of this method include:

1. Big memory consumption: each character is probably saved as 4-byte integer.
2. There is a certain limit on the size of l3intarray. According to the documentation, the length of array can only be around $$4 \times 10^6$$. On LuaTeX, the length can be longer. (But who needs this solution if there is Lua support anyways.)
\documentclass{article}
\usepackage[a4paper]{geometry}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath, amssymb}
\usepackage{datetime2}
\usepackage{expl3}

\begin{document}

\ExplSyntaxOn

\int_new:N \l_ind_int

\cs_new:Npn \to_ascii:n #1 {
\int_eval:n {#1}
}

\cs_generate_variant:Nn \intarray_gset:Nnn {Nnx}

\cs_new:Npn \fill_intarr:n #1 {
\intarray_gset:Nnx \g_tmpa_intarr {\l_ind_int} {\to_ascii:n {#1}}
\int_incr:N \l_ind_int
}

\cs_new:Npn \reverse_str:n #1 {
\str_set:Nn \l_tmpa_str {#1}

\cs_if_exist:NT \g_tmpa_intarr {
\cs_gset_eq:NN \g_tmpa_intarr \undefined
}

\intarray_new:Nn \g_tmpa_intarr {\str_count:N \l_tmpa_str}

\int_set:Nn \l_ind_int {1}
\str_map_function:NN \l_tmpa_str \fill_intarr:n

\int_set:Nn \l_tmpa_int {\str_count:N \l_tmpa_str}
\int_do_while:nNnn {\l_tmpa_int} > {0} {
\int_set:Nn \l_tmpb_int {\intarray_item:Nn \g_tmpa_intarr {\l_tmpa_int}}
\exp_args:Nx \tl_to_str:n {\char_generate:nn {\l_tmpb_int}{12}}
\int_decr:N \l_tmpa_int
}
}

\newcommand{\reversestr}[1]{
\reverse_str:n {#1}
}

\ExplSyntaxOff

\par\DTMNow

\end{document}