Estoy utilizando en una aplicacion la API de Google Maps. Utilizo el autocompletar de Google y las calles me salen con tildes, pero cuando las paso a la url para obtener la distancia no me devuelve nada.

Este es el código:

    str= "Calle Doctor José Montilla Bono, Jaén";
    str2= "Gran Via, Calle Gran Vía de Colón, Granada";
    
    String urlString = "https://maps.googleapis.com/maps/api/distancematrix/json?origins=" + str + "&destinations=" + str2 + "&mode=driving&key=0000000000000000000";

Genera la url de consulta: https://maps.googleapis.com/maps/api/distancematrix/json?origins=CalleDoctorJoséMontillaBono,Jaén&destinations=GranVia,CalleGranVíadeColón,Granada&mode=driving&traffic_model=optimistic&key=0000000000

pero la aplicación me da fallo y si abro esa url obtengo esto:
>{    
>    "destination_addresses" : [],    
>    "origin_addresses" : [],    
>    "rows" : [],    
>    "status" : "INVALID_REQUEST"    
>}

¿Alguien sabe por que puede ser?

Muchas gracias
Un saludo