Find the length of the longest substring

Question

I see questions similar like this ones, but eventually, for different programming languages. I'm trying to solve this little problem:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for abcabcbb is abc, which the length is 3. For bbbbb the longest substring is b, with the length of 1.

I don't need the anwer to it but why what I have so far fails in the second iteration.

1> longest_substring:main("abcabcbb").
H: 97, T: "bcabcbb", Sub: []
Is 97 in []? false
H: 98, T: "cabcbb", Sub: 97
** exception error: no function clause matching string:chr(97,98,1) (string.erl, line 99)
     in function  longest_substring:process/2 (src/leetcode/algorithms/longest_substring.erl, line 28)
2>

This is the source code:

-module(longest_substring).

-export([main/1]).

-spec main(S :: string()) -> string().

%%%==================================================================
%%% Export
%%%==================================================================
main(S) -> process(S, "").

%%%==================================================================
%%% Internal
%%%==================================================================
process([], Sub) -> string:len(Sub);
process([H | T], Sub) ->
  io:format("H: ~w, T: ~p, Sub: ~p~n", [H, T, Sub]),
  Found = string:chr(Sub, H),
  io:format("Is ~w in ~p? ~p~n", [H, Sub, Found =/= 0]),
  % Don't know how to make this `if` thing better...
  if
    Found > 0 -> process(T, H);
    _ -> process(T, string:concat(Sub, H))
  end.

Answer 1

You have two places where you are treating character H as a string, both within the if:

if
    Found > 0 -> process(T, H);
    _ -> process(T, string:concat(Sub, H))
end.

Both appearances of H here need to be [H] instead, to form a string from the single character. (Also, your final clause in the if needs to use true, not an underscore — you should be getting a compiler error about this.)

Currently your solution returns a number, not a string. It also fails to remember any longer substring that might appear early in the string. To fix that, you need to remember the longest substring you've seen so far, which means you need another accumulator:

-module(longest_substring).
-export([main/1]).

-spec main(S :: string()) -> string().

main(S) -> process(S, {0,[]}, {0,[]}).

process([], {LL,Last}, {LG,_}) when LL > LG -> Last;
process([], _, {_,Long}) -> Long;
process([H | T], {LL,Last}=Sub, {LG,_}=Long) ->
    case string:rchr(Last, H) of
        0 ->
            process(T, {LL+1,string:concat(Last,[H])}, Long);
        N ->
            NewLast = {1+LL-N,string:substr(Last,N+1)++[H]},
            process(T, NewLast,
                    case LL > LG of
                        true ->
                            Sub;
                        false ->
                            Long
                    end)
    end.

The main/1 function passes two accumulators to process/3, each of which is a pair of a length and a list. The first accumulator tracks the current substring, and the second tracks the longest substring seen so far.

In the last clause of process/3, we first check if H is in the current substring; if not, we add it to the current substring, increase its length by 1, and call process/3 again with the tail of the string. But if H is found in the current substring, we calculate the new current substring using the return value of string:rchr/2 to preserve the longest portion of the previous substring that we can (the original solution does not do this). We then check to see if the length of the current substring is greater than the current longest substring, and if so, we make it the longest substring, or if not we throw it away and keep the current longest substring, and then continue with the tail of the string. (Note that we could also make this check for greater or equal instead of greater; this would make our function return the last longest substring we find rather than the first.)

The first two clauses of process/3 handle the case where the input string has been fully processed. They just decide if the current substring is longer than the longest seen so far and return the longer of the two. (The alternative of using a greater or equal comparison applies here as well.)

Answer 2

for fun, I propose you to avoid complex search. In this solution I create a process for each element of the list holding: the element itself, the Pid of the next process/element in the list, and the Pid of the caller.

To initiate the search, I send to each process/element an empty list.

Each time a process/element receives a list, it checks if its stored element is a member of the received list. If yes, the list is send back to the caller, if not the element is prepend to the list and the new list is sent to the next process/element to continue the evaluation.

The caller process simply waits for as many returned messages as it has sent.

I have added a stop message and a special case for the last element of the list.

-module (longer).

-compile([export_all]).

char_proc(V,Next,Caller) ->
    receive
        stop -> ok;
        Str ->
            case lists:member(V,Str) of
                true -> Caller ! Str;
                false -> send(Next,Caller,[V|Str])
            end,
            char_proc(V,Next,Caller)
    end.

send(noproc,Caller,Str) -> Caller ! Str;
send(Next,_,Str) -> Next ! Str.

find(Str) ->
    Me = self(),
    Pids = tl(lists:reverse(lists:foldl(fun(X,Acc) -> Pid = spawn(?MODULE,char_proc,[X,hd(Acc),Me]), [Pid|Acc] end,[noproc],Str))),
    [X ! [] || X <- Pids],
    R = receive_loop(0,[],length(Str)),
    [X ! stop || X <- Pids],
    R.

receive_loop(N,S,0) -> {N,S};
receive_loop(N,S,I) ->
    receive
        M when length(M) > N ->
            receive_loop(length(M),M,I-1);
        _ ->
            receive_loop(N,S,I-1)
    end.

tested in the shell:

1> c(longer).
{ok,longer}
2> longer:find("abcdad").
{4,"abcd"}
3> longer:find("abcdadtfrseqgepz").
{9,"adtfrseqg"}
4> longer:find("aaaaaaaaaaaa").    
{1,"a"}
5> longer:find("abcdatfrseqgepz"). 
{11,"bcdatfrseqg"}
6>

Note there is no guarantee about witch sub-string will be returned if it exists several solutions, it is very easy to modify the code to return either the first sub-string or all of them.