I would agree URL encode the RelayState value should resolves the issue. It is documented in TEC529287.
Anil, you should double check your encoding as mentioned by others. I also found an ACO parameter which may help, but it was designed for windows agent, you may try on any agent though.
How to Allow the NTC to Encode URLs During Redirects to Protected Resources:
DisableI18N
Specifies how the Windows credential collector (NTC) processes the TARGET URL during authentication when the characters of the TARGET URL use HTTP encoding. When the value of this parameter is no, any characters in the URL are decoded during authentication. The decoded characters are used in the redirect to the TARGET resource. When the value of this parameter is yes, characters in the TARGET URL are not decoded during authentication. Any characters using HTTP encoding remain encoded before and after authentication.
Default: No.